给定一个循环的数组 nums ，即 nums 的第一个元素可以视为是最后一个元素的下一个元素。返回 nums 中每个元素的后面第一个比他大的元素，如果不存在比他大的元素，则返回 -1。
例如，有数组 [2,3,4,1] 则返回 [3,4,-1,2] ，其中第一二个元素后面第一个比他们大的元素均是下一个元素，第三个元素是最大的，所以输出 -1，而最后一个元素的下一个元素认为是数组的第一个元素，因此是 2。
数据范围：数组长度满足 
，数组中的元素满足 
[编程题]下一个更大的数(二)
循环数组，只有最大的元素是 -1 ， 其他的元素的值肯定不为 -1, 因此这个也可以作为一种退出条件，解法一共分为两种：
第一种，遍历两轮（即遍历长度为 0~n*n ）
第二种，仅遍历一轮（即遍历长度为 0~ n）
法一： （我的做法，脑溢血解法）遍历一轮，但从最大元素下标开始逆序遍历(正序也一样)，这样的话，每个元素都可以将其正确赋值，因为这种方式遍历时，遍历到每个元素时最大元素已经在站中存在：
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;
} 第三种解法，因为无法确认最大元素下标，因此最开始无法将最大元素的值正确设置为 -1 , 通过取余数来获取真实的下标, 遍历两轮能确保覆盖到最大元素，从而可以修正其他因为初始元素选择的较小而被错误地赋值为 -1 的元素的值：
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; 总结： 最推荐第二种
发表于 2024-05-13 16:47:37
回复(1)
import java.util.*;
import java.util.stream.Collectors;
/**
* NC354 下一个更大的数(二)
* @author d3y1
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型ArrayList
* @return int整型ArrayList
*/
public ArrayList<Integer> nextBigger (ArrayList<Integer> nums) {
// return solution1(nums);
// return solution11(nums);
// return solution111(nums);
return solution1111(nums);
// return solution2(nums);
// return solution22(nums);
}
/**
* 单调栈: 单调减(从右往左)
* @param nums
* @return
*/
private ArrayList<Integer> solution1(ArrayList<Integer> nums){
int n = nums.size();
Stack<Integer> stack = new Stack<>();
ArrayList<Integer> list = new ArrayList<>(n);
for(int i=n-1; i>=0; i--){
while(!stack.isEmpty() && stack.peek()<=nums.get(i)){
stack.pop();
}
list.add(0, stack.isEmpty()?-1:stack.peek());
stack.push(nums.get(i));
}
for(int i=n-1; i>=0; i--){
while(!stack.isEmpty() && stack.peek()<=nums.get(i)){
stack.pop();
}
list.set(i, stack.isEmpty()?-1:stack.peek());
stack.push(nums.get(i));
}
return list;
}
/**
* 单调栈: 单调减(从右往左)
* @param nums
* @return
*/
private ArrayList<Integer> solution11(ArrayList<Integer> nums){
int n = nums.size();
Stack<Integer> stack = new Stack<>();
int[] results = new int[n];
for(int i=n-1; i>=0; i--){
while(!stack.isEmpty() && stack.peek()<=nums.get(i)){
stack.pop();
}
results[i] = stack.isEmpty()?-1:stack.peek();
stack.push(nums.get(i));
}
for(int i=n-1; i>=0; i--){
while(!stack.isEmpty() && stack.peek()<=nums.get(i)){
stack.pop();
}
results[i] = stack.isEmpty()?-1:stack.peek();
stack.push(nums.get(i));
}
ArrayList<Integer> list = Arrays.stream(results) // 创建IntStream
.boxed() // 将IntStream转换为Stream<Integer>
.collect(Collectors.toCollection(ArrayList::new));
return list;
}
/**
* 单调栈: 单调减(从右往左)
* @param nums
* @return
*/
private ArrayList<Integer> solution111(ArrayList<Integer> nums){
int n = nums.size();
Stack<Integer> stack = new Stack<>();
int[] results = new int[n];
for(int i=2*n-1; i>=0; i--){
// 单调栈 单调减(从右往左)
while(!stack.isEmpty() && stack.peek()<=nums.get(i%n)){
stack.pop();
}
results[i%n] = stack.isEmpty()?-1:stack.peek();
stack.push(nums.get(i%n));
}
ArrayList<Integer> list = Arrays.stream(results) // 创建IntStream
.boxed() // 将IntStream转换为Stream<Integer>
.collect(Collectors.toCollection(ArrayList::new));
return list;
}
/**
* 单调栈: 单调减(从右往左)
* @param nums
* @return
*/
private ArrayList<Integer> solution1111(ArrayList<Integer> nums){
int n = nums.size();
Stack<Integer> stack = new Stack<>();
ArrayList<Integer> list = new ArrayList<>(n);
for(int i=0; i<n; i++){
list.add(-1);
}
for(int i=2*n-1; i>=0; i--){
// 单调栈 单调减(从右往左)
while(!stack.isEmpty() && stack.peek()<=nums.get(i%n)){
stack.pop();
}
list.set(i%n, stack.isEmpty()?-1:stack.peek());
stack.push(nums.get(i%n));
}
return list;
}
/**
* 单调栈: 单调减(从左往右)
* @param nums
* @return
*/
private ArrayList<Integer> solution2(ArrayList<Integer> nums){
int n = nums.size();
Stack<Integer> stack = new Stack<>();
ArrayList<Integer> list = new ArrayList<>(n);
for(int i=0; i<n; i++){
list.add(-1);
}
for(int i=0; i<n*2; i++){
// 单调栈 单调减(从左往右)
while(!stack.isEmpty() && nums.get(stack.peek())<nums.get(i%n)){
list.set(stack.pop(), nums.get(i%n));
}
stack.push(i%n);
}
return list;
}
/**
* 单调栈: 单调减(从左往右)
* @param nums
* @return
*/
private ArrayList<Integer> solution22(ArrayList<Integer> nums){
int n = nums.size();
Stack<Integer> stack = new Stack<>();
int[] results = new int[n];
Arrays.fill(results, -1);
for(int i=0; i<n*2; i++){
// 单调栈 单调减(从左往右)
while(!stack.isEmpty() && nums.get(stack.peek())<nums.get(i%n)){
results[stack.pop()] = nums.get(i%n);
}
stack.push(i%n);
}
ArrayList<Integer> list = Arrays.stream(results) // 创建IntStream
.boxed() // 将IntStream转换为Stream<Integer>
.collect(Collectors.toCollection(ArrayList::new));
return list;
}
}
发表于 2025-02-08 13:14:43
回复(0)
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
}
发表于 2023-03-28 21:26:31
回复(0)
# -*- 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
发表于 2022-06-23 14:32:31
回复(0)
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;
}
}
发表于 2022-04-29 16:12:37
回复(0)
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;
}
}
发表于 2022-03-20 19:19:14
回复(0)
问题信息
难度：
6条回答
19收藏
4141浏览
通过挑战的用户
查看代码-
2022-09-14 21:15:27
-
2022-09-13 11:27:41
-
2022-09-12 13:53:17 -
2022-09-12 12:06:16
-
2022-09-07 18:10:11
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
