单调栈|42.接雨水

本文主要是介绍单调栈|42.接雨水，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

力扣题目链接

class Solution {
public:int trap(vector<int>& height) {if (height.size() <= 2) return 0; // 可以不加stack<int> st; // 存着下标，计算的时候用下标对应的柱子高度st.push(0);int sum = 0;for (int i = 1; i < height.size(); i++) {if (height[i] < height[st.top()]) {     // 情况一st.push(i);} if (height[i] == height[st.top()]) {  // 情况二st.pop(); // 其实这一句可以不加，效果是一样的，但处理相同的情况的思路却变了。st.push(i);} else {                                // 情况三while (!st.empty() && height[i] > height[st.top()]) { // 注意这里是whileint mid = st.top();st.pop();if (!st.empty()) {int h = min(height[st.top()], height[i]) - height[mid];int w = i - st.top() - 1; // 注意减一，只求中间宽度sum += h * w;}}st.push(i);}}return sum;}
};

这题解法很多，我们可以都看看~

代码随想录 (programmercarl.com) 

这篇关于单调栈|42.接雨水的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---