?LeetCode刷題實戰(zhàn)503：下一個更大元素 II
Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums.
The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return -1 for this number.
示例? ? ? ? ? ? ? ? ? ? ? ? ?
輸入: [1,2,1]
輸出: [2,-1,2]
解釋: 第一個 1?的下一個更大的數是 2；
數字 2?找不到下一個更大的數；
第二個 1?的下一個最大的數需要循環(huán)搜索，結果也是 2。
注意: 輸入數組的長度不會超過 10000。
解題
class?Solution?{
public:
????vector<int> nextGreaterElements(vector<int>& nums) {
????????vector<int>res(nums.size(),0);
????????stack<int> st;
????//使用單調棧第一次遍歷
????????for(int?i=nums.size()-1;i>=0;--i){
????????????while(!st.empty()&&st.top()<=nums[i]){
????????????????st.pop();
????????????}
????????????st.push(nums[i]);
????????}
????//使用單調棧第二次遍歷，保存相關的結果
????????for(int?i=nums.size()-1;i>=0;--i){
????????????while(!st.empty()&&st.top()<=nums[i]){
????????????????st.pop();
????????????}
????????????if(st.empty()){
????????????????res[i]=-1;
????????????}
????????????else{
????????????????res[i]=st.top();
????????????}
????????????st.push(nums[i]);
????????}
????????return?res;
????}
};
評論
圖片
表情