Leetcode-面试题17.21-直方图的水量

Leetcode-面试题17.21-直方图的水量

题目描述

• 给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。

• 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1]表示的直方图，在这种情况下，可以接 6 个单位的水（蓝色部分表示水）。

示例:

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

思路一 ： 单调栈

算法思路

• 维护一个单调栈，单调栈存储的是下标，满足从栈底到栈顶的下标对应的数组 height 中的元素递减。（单调递减栈）

• 从左到右遍历数组，遍历到下标 i 时，如果栈内至少有两个元素，记栈顶元素为 top，top 的栈内下面一个元素是left，则一定有 height[left]≥height[top]。

• 如果 height[i]>height[top]，则得到一个可以接雨水的区域，该区域的宽度是 i−left−1，高度是min(height[left],height[i])−height[top]，根据宽度和高度即可计算得到该区域能接的水的量。

  • 为了得到left , 需要将top 进行出栈。在对top计算能接的水量之后，left变成新的top。
  • 重复上述操作，直到栈变为空，或者栈顶下标对应的height中元素大于或等于 height[i]
  • 在对下标i 处计算能接的水量之后，将i入栈，继续遍历后面的下标，计算能接的水量
  • 遍历结束之后累加和就是能接的总水量

下面用一个例子height=[0,1,0,2,1,0,1,3,2,1,2,1]来帮助理解单调栈的做法。

class Solution {
    public int trap(int[] height) {
        // 1. 初始化变量和栈
        Deque<Integer> stack = new LinkedList<Integer>();
        int n = height.length;
        int ans = 0;                                                            // 用于记录最终结果

        // 2. 处理逻辑:遍历数组中每一个元素的下标
        for(int i = 0;i < n;i++){
            while(!stack.isEmpty() && height[i] > height[stack.peek()]){        // 保证栈内元素对应的数组中的值是单调递减的
                int top = stack.pop();                                          // 拿到栈顶的元素,并且弹出
                if(stack.isEmpty()){                                            // 如果此时栈为空，说明没有left的存在，即无法围成面积
                    break;
                }
                int left = stack.peek();                                        // 拿到此时对应的left，不弹出
                int currwidth  = i - left - 1;                                  // 宽
                int currHeight = Math.min(height[i],height[left]) - height[top];// 高
                ans += currHeight * currwidth;                                  // 面积进行累加 
        }
            // 3. 当前区域面积计算完，对新元素入栈
            stack.push(i);   
        }
        return ans;                                                       
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 height 的长度。从 0 到 n−1 的每个下标最多只会入栈和出栈各一次。

• 空间复杂度：O(n)，其中 n 是数组 height 的长度。空间复杂度主要取决于栈空间，栈的大小不会超过 n。

打赏