https://leetcode.com/problems/steps-to-make-array-non-decreasing/
又是单调栈的题目，又一次踩坑，没有这个意识啊。

个人解答

  1. class Solution:
  2.     def totalSteps(self, nums: List[int]) -> int:
  3.         res = 0
  4.         stk = [] # (i, opCnt to delete right)
  5.         for i in range(len(nums) - 1, -1, -1):
  6.             currOpCnt = 0
  7.             while stk and nums[stk[-1][0]] < nums[i]:
  8.                 currOpCnt = max(currOpCnt + 1, stk[-1][1])
  9.                 stk.pop()
  10.             stk.append((i, currOpCnt))
  11.             res = max(res, currOpCnt)
  12.         return res

题目分析

这道题的问题转化确实不是那么容易能想到的，就直接照搬hint了。

  • 一个元素要不要被删除，取决于左侧有没有比它更大的元素。
  • 如果要被删除，要计算出第几轮被删除，最多轮才能被删除的元素，其轮数就是想要的结果了。

好，问题转化清楚了，计算一个元素右边比它小的数量，这个可以通过单调栈解决。
但是如何计算出一个元素要第几轮被删除还要费一番功夫，这又要用到dp的思想了。
比较难想到，也比较难讲清楚（需要之后再看看，写得更清楚一点）。
对于nums[i]，记录把它右边比它小的删掉需要多少次操作。
一般来说，右边有个比nums[i]小的单调递增序列，就需要这个序列长度的轮数，比如[10, 1, 2, 3]就需要3轮。
但不能只这么算，因为有可能：[10, 3, 1, 2, 3]，对于i = 1，清除右边比它小的需要两个，但对于i = 0，10右侧的单调序列是[3, 3]，好像只需要2轮的样子，但其实完全清掉需要3轮。因为清除[3, 1, 2]需要2轮。
所以应当是，对于右侧的单调序列中的元素：

  • 如果其右侧还有元素，那么需要清除其右侧元素的轮数
  • 如果没有，那么就是需要一轮

这也就是下边这一核心代码的来源：

  1. currOpCnt = max(currOpCnt + 1, stk[-1][1])

比较绕，但是意思是这么个意思，还是很精妙的一道题！