Re: [閒聊] 每日leetcode
962. Maximum Width Ramp
## 思路
先建個遞減的stack存index
再從後面掃回來(j) 檢查stack, 遇到<=的就pop並更新max width
Ex. [9,8,1,0,1,9,4,0,4,1]
stack = [0,1,2,3] # 9,8,1,0
max_width = 9 (num:1) - 2 (num:1) = 7
## Code
```python
class Solution:
def maxWidthRamp(self, nums: List[int]) -> int:
n = len(nums)
res = 0
stack = [0] # decreasing
for i in range(1, n):
if nums[stack[-1]] > nums[i]:
stack.append(i)
for j in range(n-1, -1, -1):
while stack and nums[stack[-1]] <= nums[j]:
res = max(res, j - stack.pop())
return res
```
--
https://i.imgur.com/kyBhy6o.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.32 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1728524478.A.372.html
討論串 (同標題文章)
完整討論串 (本文為第 967 之 1553 篇)：