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-- { for len(stack) > 0 && nums[i] >= nums[stack[len(stack)-1]] { ans = max(ans, i-stack[len(stack)-1]) stack = stack[:len(stack)-1] } if ans == i { return ans } } return ans } func max(i,j int)int{ if i>j{ return i } return j } -- ※ 發信站: 批踢踢實業坊(web-ptt.org.tw), 來自: 111.71.212.203 (臺灣) ※ 文章網址: https://web-ptt.org.tw/Marginalman/M.1728560371.A.98E

→ Firstshadow: 大師 以後能內推本肥肥ㄇ 10/10 19:39