[筆記] LeetCode 刷題記錄 (155,456,946) – 9 @地瓜大的飛翔旅程

章節連結

題目

155. Min Stack
496. Next Greater Element I
946. Validate Stack Sequences

歷次 LeetCode 刷題記錄

LeetCode 在需要接觸演算碼的工程師中，為相當知名的練習場所。當你有需要挑戰自己的腦筋、面試前的準備……等，都滿適合來這邊看一下你的演算法和資料結構的熟悉程度。這回要筆記的有 Min Stack、Next Greater Element I、Validate Stack Sequences。

題目

155. Min Stack

[連結]：https://leetcode.com/problems/min-stack/

/* 
*  1. 用 array 的特性來實作 stack
*/
var MinStack = function() {
    this.items = []
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.items.push(x)
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    this.items.pop()
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.items[this.items.length-1]
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    return Math.min(...this.items)
};

* 1. 用 array 的特性來實作 stack

var MinStack = function() {

this.items = []

};

/**

* @param {number} x

* @return {void}

MinStack.prototype.push = function(x) {

this.items.push(x)

};

/**

* @return {void}

MinStack.prototype.pop = function() {

this.items.pop()

};

/**

* @return {number}

MinStack.prototype.top = function() {

return this.items[this.items.length-1]

};

/**

* @return {number}

MinStack.prototype.getMin = function() {

return Math.min(...this.items)

};

496. Next Greater Element I

[連結]：https://leetcode.com/problems/next-greater-element-i/

/**
 * 1. 將 nums1 內的每一個元素遍歷，找到在第二個陣列裡對應元素的 index
 * 2. 從其 index 右邊一個起始比較，如果有比較大的就存到 value
 * 3. 推送結果到 result。
 */

var nextGreaterElement = function(nums1, nums2) {
    let result = []
    
    nums1.forEach(item=>{
        const start = nums2.indexOf(item)
        let value = -1
        
        for(let i=start+1;i<nums2.length;i++){
            if(nums2[i]>item){
                value = nums2[i]
                break
            }
        }
        result.push(value)
    })

    return result
};

/**

* 1. 將 nums1 內的每一個元素遍歷，找到在第二個陣列裡對應元素的 index

* 2. 從其 index 右邊一個起始比較，如果有比較大的就存到 value

* 3. 推送結果到 result。

var nextGreaterElement = function(nums1, nums2) {

let result = []

nums1.forEach(item=>{

const start = nums2.indexOf(item)

let value = -1

for(let i=start+1;i<nums2.length;i++){

if(nums2[i]>item){

value = nums2[i]

break

}

result.push(value)

})

return result

};

946. Validate Stack Sequences

[連結]：https://leetcode.com/problems/validate-stack-sequences/

/**
 * 1. 用一個 array 來儲存 stack 的流程，並給定 poppedIndex = 0
 * 2. 依序將 pushed 的每個值推入 stack
 * 3. 推入後，若出現和 popped 內的元素相同時，將 poppedIndex+1，並將 stack 內的元素 pop()
 */
var validateStackSequences = function(pushed, popped) {
    let stack = []
    let poppedIndex = 0
        
    for(let i=0; i<pushed.length;i++){
        stack.push(pushed[i])
        while(popped[poppedIndex]===stack[stack.length-1] && (stack.length !== 0)){
            stack.pop()
            poppedIndex += 1
        }
    }

    return poppedIndex === pushed.length
};