LeetCode-42 接雨水⭐

📝题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

📝思路

想法一：动态规划。对于每一列，找到该列左边最高的墙和右边最高的墙，根据木桶效应，取矮的那面墙与该列比较，若高于该列，则该列可蓄水。为避免重复计算左右最高墙高度，采用动态规划思想记忆化存储。
想法二：栈。在遍历数组时维护一个栈。如果当前的条形块小于或等于栈顶的条形块，则将条形块的索引入栈，意思是当前的条形块被栈中的前一个条形块界定。如果一个条形块长于栈顶，可以确定栈顶的条形块被当前条形块和栈的前一个条形块界定，因此弹出栈顶元素并且累加。

算法详细过程：

• 使用栈来存储条形块的索引下标。
• 遍历数组：
  • 当栈非空且height[current] > height[st.top()]
    • 意味着栈中元素可以被弹出。弹出栈顶元素top。
    • 计算当前元素和栈顶元素的距离，准备进行填充操作: distance = current−st.top()−1
    • 找出界定高度bounded_height = min(height[current], height[st.top()])
    • 累加
  • 将当前索引下标入栈
  • 将 current 移动到下个位置

🐣：看到题解前的乱七八糟的思路真是疯狂，疯狂WA，疯狂修改，脆败🙇‍♀️

📝题解

//想法一

int trap(vector<int>& height) {
    int len = height.size();
    if (len < 3)    return 0;
    int max_left[len], max_right[len];
    max_left[0] = height[0];
    max_right[len-1] = height[len-1];
    for (int i = 1; i < len-1; ++i)
        max_left[i] = max(max_left[i-1], height[i-1]);
    
    for (int i = len-2; i >= 0; --i)
        max_right[i] = max(max_right[i+1], height[i+1]);

    int result = 0;
    for (int i = 1; i < len-1; ++i){
        int min_height = min(max_left[i], max_right[i]);
        if (height[i] < min_height) result = result+min_height-height[i];
    }
    return result;
}

//想法二

int trap(vector<int>& height) {        
    int len = height.size();
    int result = 0, current = 0;
    stack<int> index;
    while (current < len){
        while (!index.empty() && height[current]>height[index.top()]){
            int tmp_h = height[index.top()];
            index.pop();
            if (index.empty())  break;
            int distance = current-index.top()-1;
            int min_h = min(height[current], height[index.top()]);
            result += distance*(min_h-tmp_h);
        }
        index.push(current);
        ++current;
    }
    return result;
}