找出数组中每个数右边第一个比它大的元素
找出数组中每个数右边第一个比它大的元素
1.题目描述
题目:给定一个整型数组,数组元素随机无序的,要求打印出所有元素右边第一个大于该元素的值。 如数组A=[1,5,3,6,4,8,9,10] 输出[5, 6, 6, 8, 8, 9, 10, -1] 如数组A=[8, 2, 5, 4, 3, 9, 7, 2, 5] 输出[9, 5, 9, 9, 9, -1, -1, 5, -1]
2.思路(单调栈)
(1)初始化栈:插入数组第一个元素的下标0。 (2)如果栈非空并且遍历到的数组元素比栈顶元素指向的元素大,则栈顶元素出栈,结果数组对应的索引赋值为遍历到的元素。res[s.top()] = nums[index]。 (3)否则把遍历到的元素入栈,index++。 (4)当遍历完数组时,如果栈非空,则栈中元素依次出栈,且结果数组对应索引的值赋值为-1。表示找不到右边第一个比它大的元素。
3.代码
vector<int> findMaxRightWithStack(vector<int>& nums) { if(nums.empty()) { return nums; } int size = nums.size(); vector<int> res(size); stack<int> s; s.push(0); int index = 1; while(index < size) { if(!s.empty() && nums[index] > nums[s.top()]) { res[s.top()] = nums[index]; s.pop(); } else { s.push(index); index++; } } if(!s.empty()) { res[s.top()] = -1; s.pop(); } return res; }
4.复杂度分析
时间复杂度:O(n) 空间复杂度:O(n)
下一篇:
经典例题——字母图形(LQ)