Re: [閒聊] 每日leetcode
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
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.212.203 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1728560371.A.98E.html
→
10/10 19:39,
1年前
, 1F
10/10 19:39, 1F
討論串 (同標題文章)
完整討論串 (本文為第 971 之 1554 篇)：