代码随想录算法训练营第五十五天-42. 接雨水

• 暴力解法：
  • 遍历每根柱子，对每根柱再遍历右边比其高手柱子，和左边比其高的柱子，根据凹槽深度来求解容量
  • 优化：预处理，即先存每根柱子右边比其高的柱子是哪一个到第一个数组，再用另一个数组来存其左边比其高的柱子是哪一个
• 单调栈：题目比较类似每日温度
  • 这道题是要找三个元素的位置
    • 第一个元素就是遍历中的元素，用当前遍历的下标值来确定
    • 第二个元素就是第一个右边比其大的元素，这个就是要满足条件即将压入栈中的元素
    • 第三个元素就是第一个左边比其大的元素，这个元素就在栈中紧跟着要出栈的元素
  • 这个栈的作用是什么（补充知识点）
    • 之前遍历过的元素
    • 只有这样，当前遍历的元素才可能是栈中元素右边第一个比其（栈顶元素）大的元素
  • 这道题对栈顶元素与当前遍历元素值相等的情况，我选择不处理，直接跳到下一个元素

class Solution {
public:
    int trap(std::vector<int>& heights) {
        int len = heights.size(), sum = 0;
        if (len <= 2) {
            return 0;
        }
        std::stack<int> heights_indices;
        heights_indices.push(0);
        for (int i = 1; i < len; ++i) {
            if (heights[i] < heights[heights_indices.top()]) {
                heights_indices.push(i);
            } else if (heights[i] > heights[heights_indices.top()]) {
                while (!heights_indices.empty() && heights[i] > heights[heights_indices.top()]) {
                    int bottom_index = heights_indices.top();
                    heights_indices.pop();
                    if (!heights_indices.empty()) {
                        int min_height = std::min(heights[i], heights[heights_indices.top()]);
                        sum += (min_height - heights[bottom_index]) * (i - heights_indices.top() - 1);
                    }
                }
                heights_indices.push(i);
            }
        }
        return sum;
    }
};

• 汇总