LeetCode Hot 100-739每日温度_leetcode 统计淹没在水下的木板数

每日温度

题目描述

根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

这一题说白了就是遍历数组，找数组中每个元素右边第一个比他大的元素，对应的值就是下标的差，如下表

我用的是暴力解法，果然没有过，贴上我的代码

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        result = []
        if not T:
            return
        previous = 0
        tmp = 0
        for i in range(len(T)):
            has_bigger = False
            if previous < T[i]:
                left = i + 1
            else:
                left = tmp
            for j in range(left, len(T)):
                if T[j] > T[i]:
                    has_bigger = True
                    result.append(j - i)
                    tmp = j
                    break
            if not has_bigger:
                result.append(0)
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

然后熟练的点击了解题

发现了一个单调栈的东西

• 单调栈
• 作用：
  可以以 O(1) 的时间复杂度得知某个位置左右两侧比他大（或小）的数的位置，当你需要高效率获取某个位置左右两侧比他大（或小）的数的位置的的时候就可以用到单调栈。

百度了一下还有一个类似的题目，也贴出来

问题描述
地上从左到右竖立着 n 块木板，从 1 到 n 依次编号，如下图所示。我们知道每块木板的高度，在第 n 块木板右侧竖立着一块高度无限大的木板，现对每块木板依次做如下的操作：对于第 i 块木板，我们从其右侧开始倒水，直到水的高度等于第 i 块木板的高度，倒入的水会淹没 ai 块木板（如果木板左右两侧水的高度大于等于木板高度即视为木板被淹没），求 n 次操作后，所有 ai 的和是多少。如图上所示，在第 4 块木板右侧倒水，可以淹没第 5 块和第 6 块一共 2 块木板，a4 = 2。

暴力求解，是不是很像？复杂度是O(n²)，两次循环
例如现在存在5块木板
每块木板从左至右高分别为
10，5，8，12，6
从第一块木板（高度为10）右侧开始倒水，当水到达第四块木板（高度为12）时，可以淹没第一块木板
即第一块木板至第四块木板之间的木板数量，即4-1-1 = 2，a1 = 2；
也就是说：寻找在第 i 个木板右边第一个比它大的木板j，ai 就等于木板 i 和木板 j 之间的木板数
同理得到
a2=0
a3=0
a4=1
a5=0
sum = a1 + a2 +a3 +a4 +a5 = 3

单调栈求解
单调栈来求解的话，复杂度是O(n)
结合单调栈的性质：使用单调栈可以找到元素向左遍历第一个比他小的元素，也可以找到元素向左遍历第一个比他大的元素。
顾名思义，单调栈就是栈内元素单调递增或者单调递减的栈，这一点和单调队列很相似，但是单调栈只能在栈顶操作。
单调栈有以下两个性质：
1、若是单调递增栈，则从栈顶到栈底的元素是严格递增的。若是单调递减栈，则从栈顶到栈底的元素是严格递减的。
2、越靠近栈顶的元素越后进栈。
单调栈与单调队列不同的地方在于栈只能在栈顶操作，因此一般在应用单调栈的地方不限定栈的大小，否则可能会造成元素无法进栈。
元素进栈过程：对于单调递增栈，若当前进栈元素为e，从栈顶开始遍历元素，把小于e或者等于e的元素弹出栈，直接遇到一个大于e的元素或者栈为空为止，然后再把e压入栈中。对于单调递减栈，则每次弹出的是大于e或者等于e的元素。

数据模拟木板倒水单调栈的入栈计算过程
思路：寻找比栈顶高的木板i，找到就出栈，不是就把木板i入栈，给出循环计数样例 10，5，8，12，6
从左往右扫描

扫描完成结束
最后栈的结构是：6，12 栈顶为6
由于最右端竖立着一块高度无限大的木板，即存在第六块木板高度为无穷，所以剩余两块木板的算法如下 a5 = 6-5-1 =0
a4 = 6-4-1 = 1
sum = a1 + a2 +a3 +a4 +a5 = 3
因此本题可以在