• Leetcode 3523. Make Array Non-decreasing
  • 1. 解題思路
  • 2. 代碼實現

• 題目鏈接：3523. Make Array Non-decreasing

1. 解題思路

這一題思路上來說就是一個棧的問題，就是從后往前依次考察每一個元素，顯然，當前位置要么被舍棄，要么被保留，但是無論如何其對應位置一定會留下一個至少不小于當前元素大小的新元素，因此，后續所有比起更小的元素都無法被保留。

由此，這就變成了一個標準的棧的問題，但是需要注意的是，如果完全使用棧，還是會出現超時的問題，因此我們對相同元素進行了合并，這樣的話可以優化效率，使之可以通過全部測試。

2. 代碼實現

給出python代碼實現如下：

class Solution:def maximumPossibleSize(self, nums: List[int]) -> int:# n = len(nums)ans = []for x in nums[::-1]:while ans != [] and ans[0][0] < x:ans.pop(0)if ans == [] or ans[0][0] > x:ans.insert(0, (x, 1))else:ans[0] = (ans[0][0], ans[0][1] + 1)return sum([x[1] for x in ans])

提交代碼評測得到：耗時356ms，占用內存37.8MB。