算法日记day 45（单调栈之每日温度|接雨水）

一、每日温度

题目：

给定一个整数数组 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]

思路：

使用一个栈结构，将第一位元素的下标值0压入栈中，分有三种情况

第一种，如果之后遍历的元素值小于栈顶压入的元素，将该元素的下标压入栈中

第二种：如果遍历的元素等于栈顶元素，同样也不做操作，将该下标值压入栈中 

第三种，如果遍历的元素值大于栈顶元素，用该下标减去栈顶元素下标，并将栈顶元素弹出，继续用该元素与新的栈顶元素比较，如果小于等于，则压入栈，如果大于，重复第三步操作

代码：

public int[] dailyTemperatures(int[] temperatures) {
    int len = temperatures.length; // 获取温度数组的长度
    Deque<Integer> stack = new LinkedList<>(); // 创建一个栈，用于存储温度的索引
    int[] res = new int[len]; // 初始化结果数组，用于存储每一天的等待天数
 
    stack.push(0); // 将第一个元素的索引压入栈中
 
    for (int i = 1; i < len; i++) { // 从第二天开始遍历温度
        // 如果当前温度小于等于栈顶索引对应的温度，压入栈中
        if (temperatures[i] <= temperatures[stack.peek()]) {
            stack.push(i);
        } else {
            // 当前温度大于栈顶索引对应的温度，处理栈中所有小于当前温度的索引
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                res[stack.peek()] = i - stack.peek(); // 计算等待天数
                stack.pop(); // 移除栈顶元素
            }
            stack.push(i); // 将当前温度的索引压入栈中
        }
    }
    return res; // 返回结果数组
}

• len 是温度数组的长度。
• stack 是一个栈，用于存储温度的索引。
• res 是一个数组，用于存储每一天的等待天数。
• 初始将第一个温度的索引 0 压入栈中。
• 从第二天（索引 1）开始遍历温度数组。
• 如果当前温度小于或等于栈顶索引对应的温度，将当前索引 i 压入栈中。
• 当前温度大于栈顶索引对应的温度，计算等待天数。
• 对栈中所有小于当前温度的索引进行处理：
  • 更新结果数组 res，计算从栈顶索引到当前索引 i 的天数差。
  • 移除栈顶元素。
• 将当前索引 i 压入栈中，准备处理后续的温度。
• 返回包含每一天的等待天数的数组 res。

二、接雨水 

题目：

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

示例 1：

输入：height = [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 个单位的雨水（蓝色部分表示雨水）。 

示例 2：

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

思路：

用单调栈的结构，压入第一个元素的下标0，循环遍历判断后面的元素值与栈顶元素值比较

如果小于栈顶元素值，则压入栈内

如果等于则代替

如果大于，则取栈顶元素为中间值并弹出栈顶元素，将遍历的元素与新的栈顶元素值比较取较小者，减去中间值得到高度h，然后栈顶元素下标值减去当前遍历的元素下标值再减一得到宽度w，最后高×宽得到面积，并记录，重复上述操作，直到遍历结束

 

代码：

public int trap(int[] height) {
    int size = height.length; // 获取高度数组的长度
    if (size <= 2) // 如果柱状图的长度小于等于2，则无法存储雨水，直接返回0
        return 0;
 
    Stack<Integer> stack = new Stack<>(); // 创建一个栈，用于存储柱子的索引
    stack.push(0); // 将第一个柱子的索引压入栈中
    int sum = 0; // 用于累加存储的雨水量
 
    for (int i = 1; i < size; i++) { // 从第二个柱子开始遍历
        if (height[i] < height[stack.peek()]) { // 当前柱子比栈顶柱子矮，直接压入栈中
            stack.push(i);
        } else if (height[i] == height[stack.peek()]) { // 当前柱子与栈顶柱子等高，移除栈顶柱子
            stack.pop();
            stack.push(i); // 重新将当前柱子的索引压入栈中
        } else { // 当前柱子比栈顶柱子高，需要计算水量
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) { // 处理栈中所有比当前柱子矮的柱子
                int mid = stack.pop(); // 弹出栈顶柱子，作为水槽的底部
                if (!stack.isEmpty()) { // 确保栈中还有柱子
                    int h = Math.min(height[i], height[stack.peek()]) - height[mid]; // 计算水的高度
                    int w = i - stack.peek() - 1; // 计算水槽的宽度
                    int hold = h * w; // 计算当前水槽能存储的水量
                    if (hold > 0) // 确保计算结果为正值
                        sum += hold; // 累加水量到总和中
                }
            }
            stack.push(i); // 将当前柱子的索引压入栈中
        }
    }
    return sum; // 返回计算的总水量
}

1. 初始化：

   • size 是柱状图的长度。
   • stack 用于存储柱子的索引。
   • sum 用于累计计算的雨水量。

2. 遍历柱状图：

   • 从第二个柱子开始遍历。
   • 如果当前柱子比栈顶柱子矮，则将当前柱子的索引压入栈中。
   • 如果当前柱子与栈顶柱子等高，则移除栈顶柱子，并将当前柱子的索引压入栈中。
   • 如果当前柱子比栈顶柱子高，处理栈中所有比当前柱子矮的柱子，并计算存储的雨水量。

3. 计算水量：

   • 弹出栈顶柱子，将其作为水槽的底部。
   • 如果栈中还有柱子，则计算水的高度和水槽的宽度，并累加计算的水量。

4. 返回结果：

   • 返回存储的雨水总量 sum。

今天的学习就到这里