单调栈,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; } };