单调栈 I：leetcode 739、402、316、321

单调栈主要是用来记录下一个比当前大或者小的数，主要解决的问题或是直接求下一个或者下n个比当前大（小）的数（位置）；或是根据当前的值无法推断出结果，需要等到下一个比当前大或者比当前小的数（位置）出现的时候才能计算。

通过观察下面题目的代码，可以得到单调栈的问题的代码模板：

    def Monostonestack(self, nums): 
        stack = []
        for i in range(len(nums)):
            while stack and nums[i] >/< nums[stack[-1]]:
                peek = stack.pop(-1)
                # 相关操作
            stack.append(i)
        return ans
1
2
3
4
5
6
7
8

leetcode 739：

题目描述：
给定一个整数数组 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 <= temperatures.length <= 105
30 <= temperatures[i] <= 100

思路： 因为是求下一次比当前温度高的位置，所以想到单调栈
这里栈内的元素是递减的

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = []
        ans = [0] * len(temperatures)
        for i in range(len(temperatures)):
            while stack and temperatures[i] > temperatures[stack[-1]]:
                peek = stack.pop(-1)
                ans[peek] = i - peek
            stack.append(i)
        return ans
1
2
3
4
5
6
7
8
9
10

leetcode 402：移掉K位数字

题目描述：
给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

示例 1 ：
输入：num = “1432219”, k = 3
输出：“1219”
解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。

示例 2 ：
输入：num = “10200”, k = 1
输出：“200”
解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

示例 3 ：
输入：num = “10”, k = 2
输出：“0”
解释：从原数字移除所有的数字，剩余为空就是 0 。

提示：
1 <= k <= num.length <= 105
num 仅由若干位数字（0 - 9）组成
除了 0 本身之外，num 不含任何前导零

思路： 因为想要的数最小，所以所得到的数的前面的位是越小越好所以想到用单调栈
栈内的元素是递增的，因为想要保存去掉K位之后最小的数
这里除了按照模板写代码，还要注意几个细节的处理：

1. 可能在入栈的过程中，删除掉的位数是小于K的，所以需要再处理一下
2. num不含先导零，所以在栈为空且要压栈的数是0的时候，这个数不如栈

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = []
        for i in range(len(num)):
            while stack and k > 0 and stack[-1] > num[i]:
                k -= 1
                stack.pop()
            if num[i] != '0' or stack:
                stack.append(num[i])
        while k > 0 and stack:  # 不能入栈的情况取反就是可以入栈的情况
            stack.pop()
            k -= 1
        if not stack:
            return '0'
        return ''.join(stack)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

leetcode 316：去除重复字母

题目描述：
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

示例 1：
输入：s = “bcabc”
输出：“abc”

示例 2：
输入：s = “cbacdcbc”
输出：“acdb”

提示：
1 <= s.length <= 104
s 由小写英文字母组成。

思路： 还是要返回一个字典序最小的字符串，且还是删除一些字母，保持原来的相对位置不变，所以想到用单调栈
这题和上一题402是相似的，只不过需要删除不是这个字符串中的一定数量，而是针对每一个字母进行一定数量的删除，所以需要先统计每个字符出现的次数；
因为要保证最后的结果中各个字符只有一次，这时不能像402题一样，最后处理集中删除一定个数，需要借助一个set，每次处理一个字符的时候，看这个字符是否已经在stack中，如果已经在不在进行处理，直接在数量上减一，经过分析可以之后就算处理，最后的作用也就是数量减一没有其他的影响；

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        stack = []
        seen = set()
        remain_counter = collections.Counter(s)
        for i in range(len(s)):
            if s[i] not in seen:
                while stack and stack[-1] > s[i] and remain_counter[stack[-1]] > 0:
                    seen.remove(stack[-1])
                    stack.pop()
                stack.append(s[i])
                seen.add(s[i])
            remain_counter[s[i]] -= 1
        return ''.join(stack)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

leetcode 321： 拼接最大数

题目描述：
给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。

求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。

示例 1:
输入:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
输出: [9, 8, 6, 5, 3]

示例 2:
输入:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
输出: [6, 7, 6, 0, 4]

示例 3:
输入:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
输出: [9, 8, 9]

思路：
这题是要在两个数组中一共选择到K个数，之前的题目是在一个数组中选择k个，所以想到，在第一个数组中选择 i 个，然后在第二个数组中选择 k-i个，再将得到的两个部分结合起来。

class Solution:
    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        def pick(k, nums):
            stack = []
            drop = len(nums) - k
            for i in range(len(nums)):
                while stack and drop > 0 and nums[i] > stack[-1]:
                    stack.pop()
                    drop -= 1
                stack.append(nums[i])
            return stack[:k]

        def merge(A, B):
            ans = []
            while A or B:
                if A > B:
                    bigger = A
                else:
                    bigger = B
                ans.append(bigger[0])
                bigger.pop(0)
            return ans

        res = []
        for i in range(0, k+1):
            if i <= len(nums1) and k-i <= len(nums2):
                if not res:
                    res = merge(pick(i, nums1), pick(k-i, nums2))
                else:
                    res = max(res, merge(pick(i, nums1), pick(k-i, nums2)))
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

这里需要注意merge函数的写法；单调栈内是递减的。

一个较好的题解总结链接