Re: [閒聊] 每日leetcode

[JIWP (神楽めあ的錢包)]

應該是昨天的

1574. Shortest Subarray to be Removed to Make Array Sorted

給一個矩陣arr 長度為n

從arr中移出一個subarray使arr中的元素為non-decreasing

請回傳subarray的最短長度

思路 :

這題我不太會講

假設刪掉subarray後的矩陣為arr*

這題就找出最長的arr*

因為只能移除一個subarray

所以arr*的開頭或結尾元素至少有一個跟arr一樣

假設arr[0]~arr[L]是non-decreasing

arr[R]~arr[n]是non-decreasing

令ans=min(n-L-1,R)

接著令i=0 , j=R

如果arr[i]<=arr[j]

i++ 且 ans=min(ans,j-i-1)

反之就

j--

這樣就可以得到答案了

golang code :

func findLengthOfShortestSubarray(arr []int) int {
        n := len(arr)
        l, r := 0, n-1
        for l < n-1 {
                if arr[l] > arr[l+1] {
                        break
                }
                l++
        }
        if l == n-1 {
                return 0
        }
        for r > 0 {
                if arr[r] < arr[r-1] {
                        break
                }
                r--
        }
        i, j := 0, r
        ans := min(n-1-l, r)
        for i <= l && j < n {
                if arr[i] <= arr[j] {
                        ans = min(ans, j-i-1)
                        i++
                } else {
                        j++
                }
        }
        return ans
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.99.213 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1731748443.A.FB2.html
→ oin1104: 大師
推 Meaverzt: 大師
推 PogChampLUL: 大師
推 dont: 大師
→ sustainer123: 大師