单调栈,c++
容器盛水问题
http://www.nowcoder.com/questionTerminal/31c1aed01b394f0b8b7734de0324e00f
为啥大家都用java代码写呢? 我一个c++,好难受,
class Solution {
public:
/**
* max water
* @param arr int整型vector the array
* @return long长整型
*/
long long maxWater(vector<int>& height) {
// write code here
// 使用 单调栈。
stack<int> st;
long long ans = 0;
for (int i = 0; i < height.size(); i ++ ) {
if (i > 0 && height[i] == height[i - 1]) continue;
while (!st.empty() && height[st.top()] < height[i]) {
int right = st.top();
st.pop();
if (st.empty()) break;
int left = st.top();
int h = min (height[i], height[left]) - height[right];
// 一定要转long long, 一开始我一直以为数据有问题。
ans = ans + (long long)h * (long long)(i - left - 1);
}
st.push(i);
}
return ans;
}
};
腾讯云智研发成长空间 229人发布
