单调栈合集402

题目

  1. 402. 移掉 K 位数字
  2. 给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
  5. 示例 1 ：
  7. 输入：num = "1432219", k = 3
  8. 输出："1219"
  9. 解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。
  10. 示例 2 ：
  12. 输入：num = "10200", k = 1
  13. 输出："200"
  14. 解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
  15. 示例 3 ：
  17. 输入：num = "10", k = 2
  18. 输出："0"
  19. 解释：从原数字移除所有的数字，剩余为空就是 0 。
  22. 提示：
  24. 1 <= k <= num.length <= 105
  25. num 仅由若干位数字（0 - 9）组成
  26. 除了 0 本身之外，num 不含任何前导零
  27. 通过次数83,164提交次数254,311

分析

  1. 输入与输出类型：字符串
  2. K：指的是需要去除的数字个数
  3. 返回值：字符串切片【K个数字】之后的最小值
  4. 问题转化:就是去除K个数字中，剩下数值最小的数值组合
  5. 数值组合的求取：每次都是俩俩比较，从前往后和从后往前的比较会直接影响数值的大小

Solution1

  1. def removeKdigits(num: str, k: int) -> str:
  2.     stack = []  # 新建一个栈
  3.     remain = len(num) - k  # 求最小数的位数
  4.     for digit in num:
  5.         while k and stack and stack[-1] > digit:  # 单调减栈，从栈底到栈顶一次递减
  6.             stack.pop()  # 指针所在位置的数字大于入栈数字，则弹出指针位置处数字
  7.             k -= 1
  8.             stack.append(digit)
  9.             return ''.join(stack[:remain]).lstrip('0') or '0'  # 列表方法去掉前导零或者直接返回零

单调栈合集739

problem

  1. 739. 每日温度
  2. 请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。
  4. 示例 1:
  6. 输入: temperatures = [73,74,75,71,69,72,76,73]
  7. 输出: [1,1,4,2,1,1,0,0]
  8. 示例 2:
  10. 输入: temperatures = [30,40,50,60]
  11. 输出: [1,1,1,0]
  12. 示例 3:
  14. 输入: temperatures = [30,60,90]
  15. 输出: [1,1,0]
  18. 提示：
  20. 1 <= temperatures.length <= 105
  21. 30 <= temperatures[i] <= 100

Solution1

  1. class Solution:
  2.     def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
  3.         # 将数组全部置为零
  4.         answer = [0] * len(temperatures)
  5.         stack = [0]
  6.         for i in range(1, len(temperatures)):
  7.             # 从栈底到栈顶为单调增栈，只有待入栈元素小于等于栈顶元素才能入栈
  8.             if temperatures[i] <= temperatures[stack[-1]]:
  9.                 stack.append(i)
  10.             else:
  11.                 # 如果待入栈元素大于栈顶元素，且栈不为空，则
  12.                 while len(stack) != 0 and temperatures[i] > temperatures[stack[-1]]:
  13.                     # 缘单调增栈，连续递增处减去上次入栈对应tp中的数值，差值即为相距天数
  14.                     answer[stack[-1]] = i - stack[-1]
  15.                     stack.pop()
  16.                 stack.append(i)
  17.         return answer
  18. """
  19. https://leetcode-cn.com/problems/daily-temperatures/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-dan-d-kwbv/
  20. https://leetcode-cn.com/problems/daily-temperatures/solution/739mei-ri-wen-du-pythondan-diao-zhan-ton-dzva/
  21. https://leetcode-cn.com/problems/daily-temperatures/solution/739-mei-ri-wen-du-by-eill123-nu5l/
  22. """

单调栈合集901

problem

  1. 901. 股票价格跨度
  2. 编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。
  4. 今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。
  6. 例如，如果未来7天股票的价格是 [100, 80, 60, 70, 60, 75, 85]，那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。
  10. 示例：
  12. 输入：["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
  13. 输出：[null,1,1,1,2,1,4,6]
  14. 解释：
  15. 首先，初始化 S = StockSpanner()，然后：
  16. S.next(100) 被调用并返回 1，
  17. S.next(80) 被调用并返回 1，
  18. S.next(60) 被调用并返回 1，
  19. S.next(70) 被调用并返回 2，
  20. S.next(60) 被调用并返回 1，
  21. S.next(75) 被调用并返回 4，
  22. S.next(85) 被调用并返回 6。
  24. 注意 (例如) S.next(75) 返回 4，因为截至今天的最后 4 个价格
  25. (包括今天的价格 75) 小于或等于今天的价格。
  28. 提示：
  30. 调用 StockSpanner.next(int price) 时，将有 1 <= price <= 10^5。
  31. 每个测试用例最多可以调用  10000 次 StockSpanner.next。
  32. 在所有测试用例中，最多调用 150000 次 StockSpanner.next。
  33. 此问题的总时间限制减少了 50%。

thinking

  1. 题目要求小于等于当前的元素，逆命题是大于当前元素

Solution1

  1. class StockSpanner:
  3.     def __init__(self):
  4.         self.stack = []  # 定义栈结构
  6.     def next(self, price: int) -> int:
  7.         weight = 1  # 既能够作为当前元素的一次计数，也可以作为计数单位
  8.         # 单调递减栈
  9.         while self.stack and self.stack[-1][0] <= price:  # 入栈元素小于当前元素
  10.             weight += self.stack.pop()[1]  # 没弹出一个元素，则计数器加一
  11.         self.stack.append((price, weight))  # 存储元组形式的数据元素，可以理解为二维数组
  12.         return weight
  14. # Your StockSpanner object will be instantiated and called as such:
  15. # obj = StockSpanner()
  16. # param_1 = obj.next(price)

单调栈合集1081

problem

  1. 返回 s 字典序最小的子序列，该子序列包含 s 的所有不同字符，且只包含一次。
  3. 注意：该题与 316 https://leetcode.com/problems/remove-duplicate-letters/ 相同
  7. 示例 1：
  9. 输入：s = "bcabc"
  10. 输出："abc"
  11. 示例 2：
  13. 输入：s = "cbacdcbc"
  14. 输出："acdb"
  17. 提示：
  19. 1 <= s.length <= 1000
  20. s 由小写英文字母组成

Solution1

  1. class Solution:
  2.     def smallestSubsequence(self, s: str) -> str:
  3.         stack = []  # 定义栈结构
  4.         for i in range(len(s)):  # 对传入参数进行遍历
  5.             if s[i] not in stack:  # 遍历的元素必须是第一次出现
  6.             # 1.栈不为空；2. 栈顶元素大于被遍历的元素；3.在被遍历的元素后面还有其他元素；
  7.                 while stack and stack[-1] > s[i] and s[i:].count(stack[-1]):
  8.                     stack.pop()
  9.                 stack.append(s[i])
  10.         return ''.join(stack)