LeetCode 在需要接觸演算碼的工程師中，為相當知名的練習場所。當你有需要挑戰自己的腦筋、面試前的準備……等，都滿適合來這邊看一下你的演算法和資料結構的熟悉程度。這回要筆記的有 Min Stack、Next Greater Element I、Validate Stack Sequences。
題目
155. Min Stack
[連結]：https://leetcode.com/problems/min-stack/
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
/* * 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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
/** * 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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
/** * 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 }; |
