给定一个循环的数组 nums ,即 nums 的第一个元素可以视为是最后一个元素的下一个元素。返回 nums 中每个元素的后面第一个比他大的元素,如果不存在比他大的元素,则返回 -1。
例如,有数组 [2,3,4,1] 则返回 [3,4,-1,2] ,其中第一二个元素后面第一个比他们大的元素均是下一个元素,第三个元素是最大的,所以输出 -1,而最后一个元素的下一个元素认为是数组的第一个元素,因此是 2
数据范围:数组长度满足 ,数组中的元素满足
[2,3,4,1]
[3,4,-1,2]
其中第一二个元素后面第一个比他们大的元素均是下一个元素,第三个元素是最大的,所以输出 -1,而最后一个元素的下一个元素认为是数组的第一个元素,因此是 2
[4,3,2,1]
[-1,4,4,4]
public static ArrayList<Integer> nextBigger(ArrayList<Integer> nums) { // write code here int len = nums.size(); ArrayList<Integer> ret = new ArrayList<>(); Stack<Integer> monoStack = new Stack<>(); // 找到最大的值的下标,从最大的开始遍历 int maxIndex = 0; ret.add(-1); for (int i = 1; i < len; i++){ ret.add(-1); if (nums.get(i) > nums.get(maxIndex)) { maxIndex = i; } } int i = maxIndex; do { while (!monoStack.isEmpty() && nums.get(i) >= nums.get(monoStack.peek())) // 如果发现了较大的数,弹出 monoStack.pop(); // 为空: 如果最后一个元素,则更新为第一个,否则为 -1, 不为空:直接更新 ret.set(i, monoStack.isEmpty() ? -1 : nums.get(monoStack.peek())); monoStack.push(i); i--; if (i == -1) i = len - 1; } while (i != maxIndex); return ret; }
public ArrayList<Integer> nextBigger(ArrayList<Integer> nums) { // write code here int size = nums.size(); ArrayList<Integer> result = new ArrayList<>(); for (int i = 0; i < size; i++) { // 全部置为-1 result.add(i, -1); } Stack<Integer> stack = new Stack<>(); // 数组double for (int i = 0; i < size; i++) { nums.add(nums.get(i)); } for (int i = 0; i < nums.size(); i++) { while (!stack.isEmpty() && nums.get(i) > nums.get(stack.peek())) { Integer pop = stack.pop(); if (pop < size) { result.set(pop, nums.get(i)); } } stack.push(i); } return result; }
public ArrayList<Integer> nextBigger (ArrayList<Integer> nums) { // write code here Stack<Integer> stack = new Stack<>(); int n = nums.size(); ArrayList<Integer> ans = new ArrayList<>(); for(int i = 0; i < n; i++){ ans.add(-1); } for(int i = 0; i < n * 2; i++){ while(!stack.isEmpty() && nums.get(i % n) > nums.get(stack.peek())){ int x = stack.pop(); ans.set(x, nums.get(i % n)); } stack.push(i % n); } return ans;
package main //import "fmt" /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @return int整型一维数组 */ func nextBigger( nums []int ) []int { n:=len(nums) ans:=make([]int,n) for i,_:=range ans{ ans[i]=-1 } stk:=[]int{} for i,x:=range append(nums,nums...){ for len(stk)>0&&nums[stk[len(stk)-1]]<x{ ans[stk[len(stk)-1]]=x stk=stk[:len(stk)-1] } stk=append(stk,i%n) } return ans }
# -*- coding: utf-8 -*- # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @return int整型一维数组 # class Solution: """ 题目: https://www.nowcoder.com/practice/3923970e95b140fdb65e6c00bcda403d?tpId=196&tqId=40444&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title= 算法: 环形数组问题: 先将数组展开,新数组看作是nums + nums[:-1],新数组的长度变为0 ~ 2*n-2;当然我们也可以对n取模,这样就不需要分配空间了 建立单调递减栈,栈中存储元素下标 遍历新数组0 ~ 2n-2: 若stack为空 或者 nums[i] < stack[-1]: 下标i%n入栈 否则: 栈顶元素出栈 res[stack[-1]] = nums[i] 复杂度: 时间复杂度:O(n) 空间复杂度:O(n), 单调栈的长度 """ def nextBigger(self, nums): # write code here n = len(nums) res, stack = [-1] * n, [] for i in range(2 * n - 1): while stack and nums[stack[-1]] < nums[i % n]: idx = stack.pop() if res[idx] == -1: res[idx] = nums[i % n] stack.append(i % n) return res if __name__ == "__main__": sol = Solution() # nums = [2, 3, 4, 1] nums = [4, 3, 2, 1] res = sol.nextBigger(nums) print res
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型ArrayList * @return int整型ArrayList */ public ArrayList<Integer> nextBigger(ArrayList<Integer> nums) { // write code here int size = nums.size(); ArrayList<Integer> result = new ArrayList<>(); for (int i = 0; i < size; i++) { // 全部置为-1 result.add(i, -1); } Stack<Integer> stack = new Stack<>(); // 数组double for (int i = 0; i < size; i++) { nums.add(nums.get(i)); } for (int i = 0; i < nums.size(); i++) { while (!stack.isEmpty() && nums.get(i) > nums.get(stack.peek())) { Integer pop = stack.pop(); if (pop < size) { result.set(pop, nums.get(i)); } } stack.push(i); } return result; } }
public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型ArrayList * @return int整型ArrayList */ public ArrayList<Integer> nextBigger (ArrayList<Integer> nums) { // write code here Stack<Integer> s = new Stack<>(); int n = nums.size(); int[] temp = new int[n]; for(int i=n*2-1;i>=0;i--){ while(!s.empty()&&s.peek()<=nums.get(i%n)){ s.pop(); } temp[i%n]=s.empty()?-1:s.peek(); s.push(nums.get(i%n)); } ArrayList<Integer> res = new ArrayList<>(); for(int i=0;i<n;i++){ res.add(temp[i]); } return res; } }