962. Maximum Width Ramp
ramp是指滿足下列條件的組合
(1)i<j
(2)nums[i]<nums[j]
而width定義為j-i
請找出nums中最大的width
沒有就回傳0
思路:
思路1:
建立一個長度跟nums一樣的arr
arr[i][0]=i
arr[i][1]=nums[i]
再把arr依照arr[i][1]的大小去排列
如果arr[i][1]=arr[j][1]，就照i、j的大小排列
最後就從頭開始遍歷arr
先更新最小的arr[i][0](minidx)再更新最大的arr[i][0]-minidx
就可以得到答案了
思路2:
建立一個arr，放nums的index
如果nums[i]比nums[arr[len(arr)-1]]還小的話，就把i放到arr裡面
這樣可以得到一個遞減矩陣
接著從nums最後一個元素i=len(nums)-1開始
如果nums[i]比arr最後一個元素指向的數字(nums[arr[len(arr)-1]])還小
就把arr最後一個元素(ans_last)pop出來
並且更新answer=max(answer,i-arr_last)
這樣就可以得到答案了
code是思路2的
golang code :
func maxWidthRamp(nums []int) int {
stack := make([]int, 0)
for i := 0; i < len(nums); i++ {
if len(stack) == 0 || nums[i] < nums[stack[len(stack)-1]] {
stack = append(stack, i)
}
}
ans := 0
for i := len(nums) - 1; i > -1; i