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

大师 以后能内推本肥肥ㄇ