Re: [閒聊] 每日leetcode

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

402. Remove K Digits

有一個array nums，裡面的元素都是非負數

現在要移除k個元素

請回傳再移除k個元素後最小的值

思路:

用一個stack儲存元素

當遇到nums[i]比目前stack最後的元素還小的時候

就把stack[len(stack)-1]Pop出來

一直重複這個動作，直到stack最後一個元素比nums[i]還小或是已經POP出k個元素

接著把nums[i] push到stack

就這樣掃過一次nums

接著如果還沒pop出k個元素就從stack的尾端繼續pop出來

記得要把stack前面的0給刪掉

golang code:

func removeKdigits(num string, k int) string {
        stack := []byte{}
        idx:=0
        for     idx<len(num){
                for len(stack)>0 && num[idx]<stack[len(stack)-1] && k>0{
                        stack=stack[:len(stack)-1]
                        k--
                }
                stack=append(stack,num[idx])
                idx++
        }
    for  k>0 && len(stack)>0{
        stack=stack[:len(stack)-1]
        k--
    }
    for len(stack)>1 && stack[0]=='0'{
        stack=stack[1:]
    }
    if len(stack)==0{
        return "0"
    }
        return string(stack)
}


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.122.247 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1712833549.A.727.html
推 SecondRun: 大師
推 wu10200512: 單調棧 我今天才在看 還沒寫