leetcode-496-Next Greater Element I

2019-11-11 02:58:19

字體：大中小

來源：轉載

供稿：網友

問題

題目：[leetcode-496]

思路

簡單題，仔細一點。

代碼

class Solution {public: vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) { int sz1 = findNums.size(); int sz2 = nums.size(); std::vector<int> ret(sz1, int()); for(int i = 0; i < sz1; ++i){ int j = 0; for(j = 0;j < sz2; ++j){ if( nums[j] == findNums[i] ) break; } if(j==sz2) ret[i] = -1; else{ int k = 0; for(k = j + 1; k < sz2; ++k){ if(nums[k] > nums[j]){ ret[i] = nums[k]; break; } } if(k==sz2) ret[i] = -1; } } return ret; }};

思路1

當然，這題有O(N)復雜度的解法。參考這個鏈接[Next Greater Element]。當然這個題目本生的意思和題面有一點不同。該題是求數組中任意一個元素的下一個較大元素。算法如下：

Method 2 (Using Stack) Thanks to pchild for suggesting following apPRoach. 1) Push the first element to stack. 2) Pick rest of the elements one by one and follow following steps in loop. ….a) Mark the current element as next. ….b) If stack is not empty, then pop an element from stack and compare it with next. ….c) If next is greater than the popped element, then next is the next greater element for the popped element. ….d) Keep popping from the stack while the popped element is smaller than next. next becomes the next greater element for all such popped elements ….g) If next is smaller than the popped element, then push the popped element back. 3) After the loop in step 2 is over, pop all the elements from stack and print -1 as next element for them.

簡言之，挨個判斷數組元素。如果棧頂比當前元素小，那么棧頂的nextGreater元素就是當前元素。繼續判斷棧頂和當前元素的關系，知道棧頂比當前元素大或者是棧空，將當前元素入棧即可。挨個判斷結束之后，棧中剩余元素的nextGreater元素均是-1

代碼1

class Solution {public: vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) { int sz1 = findNums.size(); int sz2 = nums.size(); std::vector<int> ret(sz1, int()); if(!sz1 || !sz2) return ret; std::map<int, int> mapper; std::stack<int> stk; stk.push(nums[0]); for(int i = 1; i < sz2; ++i){ while(!stk.empty() && stk.top() < nums[i] ){ mapper[stk.top()] = nums[i]; stk.pop(); } stk.push(nums[i]); } while(!stk.empty()){ mapper[stk.top()] = -1; stk.pop(); } for(int i = 0; i < sz1; ++i){ ret[i] = mapper[findNums[i]]; } return ret; }};

上一篇：C#數組

下一篇：背包問題