# LeetCode 42. 接雨水

42. Trapping Rain Water

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

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

• n == height.length
• $1 \le$ n $\le 2 \times 10^4$
• $0 \le$ height[i] $\le 10^5$

# 思路

对于数组中的每个位置，所能承接的最大雨水量 等于 该位置两侧最大高度的较小值减去当前高度的值

# Method 1: 动态规划

算法思路：

定义 leftMax [i] 表示 [0, i] 索引范围内的最大高度，rightMax [i] 表示 [i, height.size () - 1] 索引范围内的最大高度

初始化：

• leftMax[0] = height[0]
• rightMax[n - 1] = height[n - 1]

根据定义知

• leftMax[i] = max(leftMax[i - 1], height[i])
• rightMax[i] = max(rightMax[i + 1], height[i])

其中，应按 i 从小到大的顺序更新 leftMax 数组，按 i 从大到小的顺序更新 rightMax 数组

在更新完 leftMax 和 rightMax 数组后，任意位置 i 的接水量为 min (leftMax [i], rightMax [i]) - height [i] ，对其进行累加即为总的接水量

代码实现：

int trap(vector<int>& height) {
    int n = height.size();
    vector<int> leftMax(n, 0);    // leftMax[i] 表示 height[0, i] 区间内的最大值
    leftMax[0] = height[0];
    for (int i = 1; i < n; i++) { // 更新 leftMax 数组
        leftMax[i] = max(leftMax[i - 1], height[i]);
    }
    vector<int> rightMax(n, 0);   // rightMax[i] 表示 height[i, n - 1] 区间内的最大值
    rightMax[n - 1] = height[n - 1];
    for (int i = n - 2; i >= 0; i--) { // 更新 rightMax 数组
        rightMax[i] = max(rightMax[i + 1], height[i]);
    }
    int ans = 0;
    for (int i = 1; i < n; i++) { // 计算接水量
        ans += min(leftMax[i], rightMax[i]) - height[i];
    }
    return ans;
}

时间复杂度：$O(n)$，其中，$n$ 是数组 height 的长度

空间复杂度：$O(n)$

# Method 2: 双指针

由于 Method 1 中的数组 leftMax 是从左往右计算、数组 rightMax 是从右往左计算，可以使用左右指针和两个变量代替数组 leftMax 和 rightMax

算法思路：

定义指针 i 和指针 j ，以及变量 leftMax 和 rightMax ，初始时 i = 0 ，j = n − 1 ，leftMax = 0 ，rightMax = 0

• 这里定义的 leftMax 等价于 Method 1 中的 leftMax [i]
• 这里定义的 rightMax 等价于 Method 1 中的 rightMax [j]

当 i < j 时，执行循环：

• 更新 leftMax 和 rightMax

  • leftMax = max(leftMax, height[i])
  • rightMax = max(rightMax, height[j])

• 若 leftMax <rightMax ，说明位置 i 接水时的短板为左侧的最高板块，即 leftMax （因为 i 右侧的最高板块必定大于等于 rightMax ），因此，位置 i 的接水量为 leftMax - height [i] ，执行以下操作：

  • 累加接水量：ans += leftMax - height [i]
  • i 右移一位：i++

  对应于 Method 1 中的 leftMax [i] < rightMax [j] ，由于 rightMax [j] <= rightMax [i] 始终成立，所以有 leftMax [i] < rightMax [j] <= rightMax [i] ，因此， leftMax [i] 是短板

• 否则（即 rightMax <= leftMax ），说明位置 j 接水时的短板为右侧的最高板块，即 rightMax （因为 j 左侧的最高板块必定大于等于 leftMax ），因此，位置 j 的接水量为 rightMax - height [j] ，执行以下操作：

  • 累加接水量：ans += rightMax - height [j]
  • j 左移一位：j++

  对应于 Method 1 中的 rightMax [j] <= leftMax [i] ，由于 leftMax [i] <= leftMax [j] 始终成立，所以有 rightMax [j] <= leftMax [i] <= leftMax [j] ，因此， rightMax [j] 是短板

代码实现：

int trap(vector<int>& height) {
    int left = 0;
    int right = height.size() - 1;
    int leftMax = 0;
    int rightMax = 0;
    int ans = 0;
    while (left <= right) {
        leftMax = max(leftMax, height[left]);
        rightMax = max(rightMax, height[right]);
        if (leftMax < rightMax) {
            ans += leftMax - height[left];
            left++;
        } else {
            ans += rightMax - height[right];
            right--;
        }
    }
    return ans;
}

时间复杂度：$O(n)$，其中，$n$ 是数组 height 的长度

空间复杂度：$O(1)$

参考：

• LeetCode-Solution
• LeetCode

# LeetCode 739. 每日温度

739. Daily Temperatures

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1：

输入：temperatures = [73,74,75,71,69,72,76,73]
输出：[1,1,4,2,1,1,0,0]

示例 2：

输入：temperatures = [30,40,50,60]
输出：[1,1,1,0]

示例 3：

输入：temperatures = [30,60,90]
输出：[1,1,0]

提示：

• $1 \le$ temperatures.length $\le 10^5$
• $30 \le$ temperatures[i] $\le 100$

# Method: 单调栈（实现一）

# 算法思路

维护一个存储温度数组下标的单调栈 stack<int> stk ：从栈底到栈顶，下标对应的温度依次递减

如果一个下标在单调栈里，则表示其尚未找到下一次温度更高的下标。换而言之，如果下标从单调栈内出栈，则说明其找到了下一个温度更高的下标

从左往右遍历温度数组，对于温度数组中的每个元素 temperatures [i] ：

• 如果栈为空，则直接将下标 i 入栈
• 如果栈不为空，则将当前温度 temperatures [i] 与栈顶元素 stk.top () 对应温度 temperatures [stk.top ()] 进行比较，如果 temperatures [i] 大于 temperatures [stk.top ()] ，则 temperatures [i] 就是第一个大于 temperatures [stk.top ()] 的温度，因此将 answer [stk.top ()] 赋为 i - stk.top () ，并将 stk.top () 出栈。重复上述操作直到栈为空或者栈顶元素对应的温度小于等于当前温度，然后将 i 入栈

# 代码实现

// 从左往右遍历温度数组，单调栈内元素递增（从栈顶到栈底）
vector<int> dailyTemperatures(vector<int>& temperatures) {
    int n = temperatures.size();
    vector<int> answer(n, 0);
    stack<int> stk;
    for (int i = 0; i < n; ++i) {
        while (!stk.empty() && temperatures[i] > temperatures[stk.top()]) {
            answer[stk.top()] = i - stk.top(); // i 是温度高于 stk.top() 的第一天
            stk.pop();
        }
        stk.push(i);
    }
    return answer;
}

# Method: 单调栈（实现二）

# 算法思路

维护一个存储温度数组下标的单调栈 stack<int> stk ：从栈底到栈顶，下标对应的温度依次递减

如果一个下标可以入栈，其入栈前的栈顶元素 就是 第一个更高温度所对应的下标

从右往左遍历温度数组，对于温度数组中的每个元素 temperatures [i] ：

• 如果栈为空，则直接将下标 i 入栈
• 如果栈不为空，则将当前温度 temperatures [i] 与栈顶元素 stk.top () 对应温度 temperatures [stk.top ()] 进行比较，如果 temperatures [i] 大于等于 temperatures [stk.top ()] ，则将 stk.top () 出栈。重复上述操作直到栈为空或者栈顶元素对应的温度小于当前温度，此时，栈顶元素对应的温度就是 第一个大于 temperatures [i] 的温度，因此，将 answer [i] 赋为 stk.top () - i ，然后将 i 入栈

# 代码实现

// 从右往左遍历温度数组，单调栈内元素递增（从栈顶到栈底）
vector<int> dailyTemperatures(vector<int>& temperatures) {
    int n = temperatures.size();
    vector<int> answer(n, 0);
    stack<int> stk;
    for (int i = n - 1; i >= 0; --i) {
        while (!stk.empty() && temperatures[i] >= temperatures[stk.top()])
            stk.pop();
        if (stk.empty())
            answer[i] = 0;
        else
            answer[i] = stk.top() - i; // stk.top 是温度高于 i 的第一天
        stk.push(i);
    }
    return answer;
}

# 复杂度分析

时间复杂度：$O(n)$，其中 $n$ 是数组 temperatures 的长度，数组的每个下标至多入栈、出栈一次

空间复杂度：$O(n)$

# LeetCode 84. 柱状图中最大的矩形

84. Largest Rectangle in Histogram

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1：

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入：heights = [2,4]
输出：4

提示：

• 1 <= heights.length <= 10⁵
• 0 <= heights[i] <= 10⁴

# Method 1: 暴力法

可以考虑枚举矩形的宽或者高，即，有以下两种实现：

# 实现一

对于以 i 为左边界、j 为右边界的矩形，找出区间 [i, j] 范围内的最小高度（即，heights 数组在 [i, j] 区间内的最小值），记作 h ，则矩形的面积为 h * (j - i) + 1

枚举矩形的左右边界，计算出所有矩形的面积，找出最大面积

# 实现二

对于柱子 i ，可以将 heights [i] 固定为矩形的高度，然后向左右两侧拓展矩形的宽度：

• 从 i - 1 开始向左查找，找出满足 heights [left] < height [i] 的柱子 left
• 从 i + 1 开始向右查找，找出满足 heights [right] < heights [i] 的第一个柱子 right
• 此时，left 和 right 就是矩形的左右边界，即，以 heights [i] 为高度的矩形的最大范围为 [left + 1, right - 1]

因此，该矩形的宽度为 right - left - 1 ，面积为 heights [i] * (right - left - 1)

枚举矩形的高度 height [i] ，计算出所有矩形的面积，找出最大面积

以上两种实现的时间复杂度均为 $O(n^2)$，其中 $n$ 是数组 heights 的长度

对于本题而言，$O(n^2)$ 会超时

# Method 2: 栈

可以考虑按照如下方式维护一个栈：

• 如果新的元素比栈顶元素大，将新元素入栈

• 如果新的元素较小，不断地将栈内元素弹出来，直到栈顶比新元素小

从栈底到栈顶，元素是递增的，所以可称该栈为 单调递增栈

当需要执行出栈操作时，新元素就是出栈元素右侧的（相对于数组中的位置而言）、第一个小于出栈元素的元素

• 换而言之，如果以出栈元素作为矩形的高，新元素对应的下标就是矩形的右边界（对应 Method 1 中的 right ）

在执行出栈操作后，栈顶元素将会比新元素小，因此，栈顶元素就是新元素左侧的（相对于数组中的位置而言）、第一个小于新元素的元素

• 换而言之，如果以新元素作为矩形的高，栈顶元素对应的下标就是矩形的左边界

因此，我们可以定义 left 数组和 right 数组分别记录每一个矩形的左、右边界，通过 遍历 heights 数组、维护栈 来更新 left 和 right 数组

• 由于 left 数组和 right 数组记录的是元素的下标，为方便起见，我们在栈内存放数组元素的下标，而不是数组元素值（即，实际存入栈的是数组元素的下标，判断是否出栈、入栈时需要找到下标对应的数组元素值）
• 将 left 数组初始化为 -1 ，以应对 “某元素左侧的元素全都不比它小” 的情况；将 right 数组初始化为 heights.size () ，以应对 “ 某元素右侧的元素全都不比它小 ” 的情况

在更新完 left 和 right 数组以后，对于以 heights [i] 为高度的矩形，其最大面积为 heights [i] * (right [i] - left [i] - 1) 。因此，再遍历一次 heights 数组，即可得到最大矩阵面积

代码实现：

int largestRectangleArea(vector<int>& heights) {
    int n = heights.size();
    vector<int> left(n, -1); // left[i] 表示以 heights[i] 为高的矩形的左边界
    vector<int> right(n, n); // right[i] 表示以 heights[i] 为高的矩形的右边界
    
    stack<int> stk;
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && heights[stk.top()] >= heights[i]) {
            right[stk.top()] = i;
            stk.pop();
        }
        if (!stk.empty()) left[i] = stk.top();
        stk.push(i);
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, (right[i] - left[i] - 1) * heights[i]);
    }
    return ans;
}

时间复杂度：$O(n)$，其中 $n$ 是数组 heights 的长度

空间复杂度：$O(n)$

参考：

• leetcode-solution
• liweiwei1419
• ikaruga