给定一个长度为 
的可能含有重复值的数组 
，找到每一个位置 
左边最近的位置 
和右边最近的位置 
，
和 
比 
小。
请设计算法，返回一个二维数组，表示所有位置相应的信息。位置信息包括：两个数字 和 。如果不存在，则值为 -1，下标从 0 开始。
数据范围：
，
进阶：空间复杂度 )
，时间复杂度
[编程题]单调栈
单调栈题意的基本题目
找到比自己的小的左边加上右边的位置维护一个单调递增的栈，栈内元素从栈底到栈顶是单调递增
分别用两次循环，一次寻找左边的一次寻找右边的位置索引
import java.util.*; import java.util.Stack; public class Solution { public int[][] foundMonotoneStack (int[] nums) { int n=nums.length; int [][]ans=new int[n][2]; Stack<Integer> stack=new Stack<>(); for(int i=0;i<n;i++){ while(!stack.isEmpty()&&nums[stack.peek()]>=nums[i]) stack.pop(); if(stack.isEmpty()){ ans[i][0]=-1; } else{ ans[i][0]=stack.peek(); } stack.push(i); } stack.clear(); for(int i=n-1;i>=0;i--){ while(!stack.isEmpty()&&nums[stack.peek()]>=nums[i]) stack.pop(); if(stack.isEmpty()){ ans[i][1]=-1; } else{ ans[i][1]=stack.peek(); } stack.push(i); } return ans; } }
发表于 2021-06-16 15:03:22
回复(1)
import java.util.*;
public class Solution {
/**
* 使用两次单调递增栈
*
*
* @param nums int一维数组
* @return int二维数组
*/
public static int[][] foundMonotoneStack(int[] nums) {
int[][] res = new int[nums.length][2];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < nums.length; i++) {
while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
stack.pop();
}
if (stack.isEmpty())
res[i][0] = -1;
else {
res[i][0] = stack.peek();
}
stack.push(i);
}
stack.clear();
for (int i = nums.length - 1; i >= 0; i--) {
while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
stack.pop();
}
if (stack.isEmpty())
res[i][1] = -1;
else {
res[i][1] = stack.peek();
}
stack.push(i);
}
return res;
}
}
发表于 2021-11-23 15:20:34
回复(0)
保持栈底往栈顶是单调递增的，在弹栈时生成信息
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int一维数组
* @return int二维数组
*/
public int[][] foundMonotoneStack (int[] nums) {
// write code here
int[][] res = new int[nums.length][2];
for(int i = 0; i < nums.length; i++){
res[i][0] = -1;
res[i][1] = -1;
}
Stack<LinkedList<Integer>> stack = new Stack<>(); // 栈底往栈顶保持单调递增
for(int i = 0; i < nums.length; i++){
if(stack.isEmpty()){
LinkedList<Integer> list = new LinkedList<>();
list.add(i);
stack.push(list);
}else{
if(nums[i] == nums[stack.peek().peekLast()]){
stack.peek().add(i);
continue;
}else if(nums[i] < nums[stack.peek().peekLast()]){
while(!stack.isEmpty() && nums[i] < nums[stack.peek().peekLast()]){
// 单调性被破坏，开始弹栈生成信息
Iterator<Integer> list = stack.pop().iterator();
while(list.hasNext()){
int curIdx = list.next();
res[curIdx][1] = i; // 栈顶每个元素右边比它小的都是nums[i]
// 栈顶每个元素左边比它小是下面压着的数，下面没有压那就是-1
if(!stack.isEmpty())
res[curIdx][0] = stack.peek().peekLast();
else
res[curIdx][0] = -1;
}
}
}
LinkedList<Integer> list = new LinkedList<>();
list.add(i);
stack.push(list);
}
}
// 清算阶段，将栈中所有元素左边比它小的第一个数找到
while(!stack.isEmpty()){
Iterator<Integer> iter = stack.pop().iterator();
while(iter.hasNext()){
if(!stack.isEmpty())
res[iter.next()][0] = stack.peek().peekLast();
else
res[iter.next()][0] = -1;
}
}
return res;
}
}
发表于 2021-11-19 11:59:52
回复(0)
#include <errno.h>
#include <stdbool.h>
#define OK 1
#define ERROR -1
#define MEMORY_OVERFLOW -2
#define NOT !
#define DEFAULT_CAPACITY 8
#define InitStack(S) __InitStack(S, DEFAULT_CAPACITY)
typedef int Status;
// ==================== 顺序栈数据结构表示与实现 ====================
typedef int SElemType;
typedef struct {
SElemType* base;
SElemType* top;
size_t capacity;
} SqStack;
Status __InitStack(SqStack* S, int initialCapacity) {
if (initialCapacity < 1) {
printf("__InitStack ERROR: The initialCapacity %d Must be > 0!", initialCapacity);
return ERROR;
}
if (!(S->base = (SElemType*) malloc(initialCapacity * sizeof(SElemType)))) {
printf("__InitStack Memeory Overflow: %s\n", strerror(errno));
exit(MEMORY_OVERFLOW);
}
S->top = S->base;
S->capacity = initialCapacity;
return OK;
}
bool StackEmpty(SqStack* S) {
return S->top == S->base;
}
bool StackFull(SqStack* S) {
return (S->top - S->base) == S->capacity;
}
size_t StackLength(SqStack* S) {
return S->top - S->base;
}
void __large_capacity(SqStack* S) {
if (!(S->base = (SElemType*) realloc(S->base, (S->capacity << 1) * sizeof(SElemType)))) {
printf("__large_capacity Memeory Overflow: %s\n", strerror(errno));
exit(MEMORY_OVERFLOW);
}
S->top = S->base + S->capacity;
S->capacity <<= 1;
}
Status Push(SqStack* S, SElemType e) {
if (StackFull(S))
__large_capacity(S);
*S->top++ = e;
return OK;
}
Status Pop(SqStack* S, SElemType* ret) {
if (StackEmpty(S)) {
puts("Pop ERROR: The stack is empty!");
return ERROR;
}
*ret = *--S->top;
return OK;
}
SElemType GetTop(SqStack* S) {
if (StackEmpty(S)) return -0x3F3F3F3F;
return *((*S).top - 1);
}
Status DestroyStack(SqStack* S) {
free(S->base);
S->top = NULL;
return OK;
}
// ==================== 顺序栈数据结构表示与实现 ====================
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int一维数组
* @param numsLen int nums数组长度
* @return int二维数组
* @return int* returnSize 返回数组行数
* @return int** returnColumnSizes 返回数组列数
*/
int** foundMonotoneStack(int* nums, int numsLen, int* returnSize, int** returnColumnSizes) {
SqStack S1, S2; // 创建两个单调递增栈
InitStack(&S1);
InitStack(&S2);
int i, index;
int ** ans = (int**) malloc(numsLen * sizeof(int*));
*returnSize = numsLen;
*returnColumnSizes = (int*) malloc(numsLen * sizeof(int));
for (i = 0; i < numsLen; ++i) {
*(ans + i) = (int*) malloc(2 * sizeof(int));
memset(*(ans + i), -1, sizeof(*(ans + i)));
(*returnColumnSizes)[i] = 2;
}
for (i = numsLen - 1; i >= 0; --i) {
while (NOT StackEmpty(&S1) && *(nums + GetTop(&S1)) > *(nums + i)) {
Pop(&S1, &index);
*(*(ans + index)) = i;
}
Push(&S1, i);
}
for (i = 0; i < numsLen; ++i) {
while (NOT StackEmpty(&S2) && *(nums + GetTop(&S2)) > *(nums + i)) {
Pop(&S2, &index);
*(*(ans + index) + 1) = i;
}
Push(&S2, i);
}
DestroyStack(&S1); DestroyStack(&S2);
return ans;
}
发表于 2021-07-07 12:48:06
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int一维数组
* @return int二维数组
*/
public int[][] foundMonotoneStack (int[] nums) {
// write code here
LinkedList<Integer>stk=new LinkedList<>();
int[][]res=new int[nums.length][2];
for(int i=0;i<nums.length;i++){
while(!stk.isEmpty()&&nums[stk.peekLast()]>=nums[i]){
res[stk.peekLast()][1]=i;
stk.pollLast();
}
if(!stk.isEmpty()){
res[i][0]=stk.peekLast();
}else res[i][0]=-1;
stk.addLast(i);
}
while(!stk.isEmpty()){
res[stk.pollLast()][1]=-1;
}
return res;
}
}
发表于 2021-06-28 13:49:08
回复(0)
class Solution: def foundMonotoneStack(self , nums ): # write code here n = len(nums) res = [[-1, -1] for _ in range(n)] stack = [] for i in range(n): while stack and nums[stack[-1]] >= nums[i]: # 保证stack里始终从下往上递增的 stack.pop() if not stack: res[i][0] = -1 else: res[i][0] = stack[-1] # 这里stack的最上面比nums[i]小 stack.append(i) # 这里append的值肯定比pop的值要小，所以pop出来的值就没有用了 stack.clear() for j in range(n - 1, -1, -1): # 倒序 while stack and nums[stack[-1]] >= nums[j]: # 这里也是一样的逻辑，stack从下往上递增 stack.pop() if not stack: res[j][1] = -1 else: res[j][1] = stack[-1] stack.append(j) return res
发表于 2021-09-20 16:54:35
回复(0)
找左边时： 从左往右入栈，保证栈中元素比当前元素小，弹出栈顶即左边最小
找右边是： 从右往左入栈，保证栈中元素比当前元素小，弹出栈顶即右边最小
public int[][] foundMonotoneStack (int[] nums) {
// write code here
int n = nums.length;
int[][] result = new int[n][2];
Stack<Integer> stack = new Stack<>();
// 找左边最近的小于当前元素的位置
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
stack.pop();
}
result[i][0] = stack.isEmpty() ? -1 : stack.peek();
stack.push(i);
}
stack.clear();
// 找右边最近的小于当前元素的位置
for (int i = n - 1; i >= 0; i--) {
while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
stack.pop();
}
result[i][1] = stack.isEmpty() ? -1 : stack.peek();
stack.push(i);
}
return result;
}
发表于 2024-07-11 12:01:44
回复(0)
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型vector<vector<>>
*/
vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
// write code here
// 定义一个数组 保存左边界的结果
// 思路就是，从左向右开始计算，去计算每个值的左边界，存在记录，不存在就是-1
vector<int> vec1;
vec1.push_back(-1);
int n = nums.size();
for(int i=1; i<nums.size(); i++)
{
bool flag = false;
for(int j=i-1; j>=0; j--)
{
if(nums[i] > nums[j])
{
vec1.push_back(j);
flag = true;
break;
}
}
if(!flag)
vec1.push_back(-1);
}
// 定义一个右边界的数组，从右开始往左计算，计算每个值的有边界，存在记录，不存在-1
// 另外顺序是是逆序的，所有需要reverse 其实也可以直接定义一个等大的数组
// 可以节约reverse的时间
vector<int> vec2;
vec2.push_back(-1);
for(int i=n-2; i>=0; i--)
{
bool flag = false;
for(int j=i+1; j<n; j++)
{
if(nums[i] > nums[j])
{
vec2.push_back(j);
flag = true;
break;
}
}
if(!flag)
vec2.push_back(-1);
}
reverse(vec2.begin(), vec2.end());
// 重新装成输出的格式
vector<vector<int>> res;
for(int i = 0; i<n; i++)
{
res.push_back({vec1[i], vec2[i]});
}
return res;
}
};
发表于 2022-09-06 10:20:08
回复(0)
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums intvector
* @return intvector<vector<>>
*/
vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
// write code here
vector<vector<int>>ans(nums.size(),vector<int>(2));
int stack[1000]={0};
int top = 0;
//left
ans[0][0] = -1;
stack[top++] = 0;
for(int i = 1; i < nums.size(); i++)
{
while(top != 0){
if(nums[i] > nums[stack[top-1]]){
ans[i][0] = stack[top-1];
stack[top++] = i;
break;
}else{
top--;
}
}
if(top == 0){
stack[top++] = i;
ans[i][0] = -1;
}
}
//right
ans[nums.size()-1][1] = -1;
top=0;
stack[top++] = nums.size()-1;
for(int i = nums.size()-1; i >= 0; i--)
{
while(top != 0){
if(nums[i] > nums[stack[top-1]]){
ans[i][1] = stack[top-1];
stack[top++] = i;
break;
}else{
top--;
}
}
if(top == 0){
stack[top++] = i;
ans[i][1] = -1;
}
}
return ans;
}
}; L值，第一个为-1，并将第一个元素下标进栈，对于后续每个元素ai，都与栈顶下标对应的的元素比较，如果栈顶下标元素小，则ai的L值为栈顶下标，并将ai下标进栈，否则，出栈继续比较直到有L值或者栈空，栈空则说明左边没有比ai小的元素，ai的L值为-1，ai下标进栈。
R值同理，从右往左遍历。
发表于 2021-01-19 00:52:44
回复(0)
class Solution: def foundMonotoneStack(self , nums: List[int]) -> List[List[int]]: ans = [] for i in range(len(nums)): l, r = i-1, i+1 while l >= 0: if nums[l] >= nums[i]: l -= 1 else: break while r < len(nums): if nums[r] >= nums[i]: r += 1 else: break if r == len(nums): r = -1 ans.append([l,r]) return ans
发表于 2025-07-15 10:54:31
回复(0)
import java.util.*;
/**
* NC157 单调栈
* @author d3y1
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型一维数组
* @return int整型二维数组
*/
public int[][] foundMonotoneStack (int[] nums) {
int n = nums.length;
int[][] results = new int[n][2];
// 从左往右 遍历
Stack<Integer> leftStack = new Stack<>();
// 从右往左 遍历
Stack<Integer> rightStack = new Stack<>();
for(int i=0; i<n; i++){
// 左边最近位置l -> 单调栈 单调增(从左往右)
while(!leftStack.isEmpty() && nums[leftStack.peek()]>=nums[i]){
leftStack.pop();
}
if(leftStack.isEmpty()){
results[i][0] = -1;
}else{
results[i][0] = leftStack.peek();
}
leftStack.push(i);
// 右边最近位置r -> 单调栈 单调增(从右往左)
while(!rightStack.isEmpty() && nums[rightStack.peek()]>=nums[n-1-i]){
rightStack.pop();
}
if(rightStack.isEmpty()){
results[n-1-i][1] = -1;
}else{
results[n-1-i][1] = rightStack.peek();
}
rightStack.push(n-1-i);
}
return results;
}
}
发表于 2025-01-29 15:32:49
回复(0)
import java.util.*;
public class Solution {
public int[][] foundMonotoneStack (int[] nums) {
if (nums == null || nums.length == 0) {
return null;
}
int n = nums.length;
int[][] result = new int[n][2];
LinkedList<Integer> stack = new LinkedList<>();
for (int i = 0; i < n; i++) {
result[i] = new int[2];
while (!stack.isEmpty() && nums[i] <= nums[stack.peek()]) {
stack.pop();
}
int left = stack.isEmpty() ? -1 : stack.peek();
result[i][0] = left;
stack.push(i);
}
stack.clear();
for (int i = n - 1; i >= 0; i--) {
while (!stack.isEmpty() && nums[i] <= nums[stack.peek()]) {
stack.pop();
}
int right = stack.isEmpty() ? -1 : stack.peek();
result[i][1] = right;
stack.push(i);
}
return result;
}
}
发表于 2024-05-19 16:05:27
回复(0)
# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @return int整型二维数组 # class Solution: def foundMonotoneStack(self , nums: List[int]) -> List[List[int]]: # write code here min_left = [-1 for i in range(len(nums))] min_left_position = [-1 for i in range(len(nums))] stack = [0] for i in range(len(nums)): if nums[stack[-1]] >= nums[i]: while len(stack) != 0: if nums[stack[-1]] >= nums[i]: stack.pop() continue else: break if len(stack) != 0: if nums[stack[-1]] < nums[i]: min_left[i] = stack[-1] stack.append(i) min_right = [-1 for i in range(len(nums))] stack = [len(nums)-1] for i in range(len(nums)-1 - 1, -1, -1): if nums[stack[-1]] >= nums[i]: while len(stack) != 0: if nums[stack[-1]] >= nums[i]: stack.pop() continue else: break if len(stack) != 0: if nums[stack[-1]] < nums[i]: min_right[i] = stack[-1] stack.append(i) res = [] for i in range(len(nums)): res.append([min_left[i], min_right[i]]) return res
发表于 2024-05-15 22:27:32
回复(0)
双指针感觉也可以
class Solution: def foundMonotoneStack(self, nums: List[int]) -> List[List[int]]: # write code here res = [] for i in range(len(nums)): l, r = i, i while l >= 0: if nums[i] <= nums[l]: l -= 1 else: break while r < len(nums): if nums[i] <= nums[r]: r += 1 else: break if r == len(nums): r = -1 res.append([l, r]) return res
编辑于 2024-03-15 23:27:36
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int一维数组
* @return int二维数组
*/
public int[][] foundMonotoneStack (int[] nums) {
// write code here
int arr[][]=new int[nums.length][2];
for(int i=0;i<nums.length;i++){
int left=-1;
int right=-1;
//最左边
if(i==0){
//左
arr[i][0]=-1;
//右遍遍历寻找最近比arr[i]小的值
for(int j=i+1;j<arr.length;j++){
if(nums[j]<nums[i]){
right=j;
break;
}
}
arr[i][1]=right;
}
//最右边
if(i==nums.length-1){
//右
arr[i][1]=-1;
//左遍历寻找最近比arr[i]小的值
for(int j=i-1;j>=0;j--){
if(nums[j]<nums[i]){
left=j;
break;
}
}
arr[i][0]=left;
}
//中间情况
if(i!=0&&i!=nums.length-1){
//左遍历寻找最近比arr[i]小的值
for(int j=i-1;j>=0;j--){
if(nums[j]<nums[i]){
left=j;
break;
}
}
arr[i][0]=left;
//右遍历寻找最近比arr[i]小的值
for(int j=i+1;j<nums.length;j++){
if(nums[j]<nums[i]){
right=j;
break;
}
}
arr[i][1]=right;
}
}
return arr;
}
}
发表于 2023-05-24 18:10:57
回复(0)
单调递增栈。遇到小的通通出栈。
import java.util.*;
public class Solution {
public int[][] foundMonotoneStack (int[] nums) {
List<Integer> leftList = new ArrayList<>();
List<Integer> rightList = new ArrayList<>();
int[][] res = new int[nums.length][2];
for(int i = 0; i < res.length; ++i) {
res[i][0] = -1;
res[i][1] = -1;
}
for(int i = 0; i < nums.length; ++i) {
while(leftList.size() != 0 && nums[leftList.get(leftList.size() - 1)] > nums[i]) {
res[leftList.get(leftList.size() - 1)][1] = i;
leftList.remove(leftList.size() - 1);
}
while(rightList.size() != 0 && nums[rightList.get(rightList.size() - 1)] > nums[nums.length - 1 - i]) {
res[rightList.get(rightList.size() - 1)][0] = nums.length - 1 - i;
rightList.remove(rightList.size() - 1);
}
rightList.add(nums.length - 1 - i);
leftList.add(i);
}
return res;
}
}
发表于 2023-05-09 14:32:22
回复(0)
package main
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int一维数组
* @return int二维数组
*/
func foundMonotoneStack( nums []int ) [][]int {
n:=len(nums)
ans:=make([][]int,n)
for i,_:=range ans{
ans[i]=[]int{-1,-1}
}
stk1:=[]int{}
stk2:=[]int{}
for i,j:=0,n-1;i<n&&j>=0;i,j=i+1,j-1{
for len(stk1)>0&&nums[stk1[len(stk1)-1]]>nums[i]{
ans[stk1[len(stk1)-1]][1]=i
stk1=stk1[:len(stk1)-1]
}
stk1=append(stk1,i)
for len(stk2)>0&&nums[stk2[len(stk2)-1]]>nums[j]{
ans[stk2[len(stk2)-1]][0]=j
stk2=stk2[:len(stk2)-1]
}
stk2=append(stk2,j)
}
return ans
}
发表于 2023-03-09 00:47:35
回复(0)
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型vector<vector<>>
*/
vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
// write code here
vector<vector<int>> res;
for(int i = 0;i<nums.size();++i)
{
int L = -1;
int R = -1;
int val = nums[i];
for(int j = i-1;j>=0;--j)
{
if(nums[j]<nums[i])
{
L = j;
break;
}
}
for(int z = i+1;z < nums.size();++z)
{
if(nums[z]<nums[i])
{
R = z;
break;
}
}
res.emplace_back(vector<int>{L,R});
}
return res;
}
};
发表于 2022-09-15 12:16:24
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型一维数组
* @return int整型二维数组
*/
public int[][] foundMonotoneStack (int[] nums) {
// write code here
int[][] res = new int[nums.length][2];
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < nums.length; i++){
while(!stack.isEmpty() && nums[stack.peek()] > nums[i]){
int j = stack.pop();
res[j][1] = i;
}
if(stack.isEmpty() || nums[stack.peek()] == nums[i]){
res[i][0] = -1;
}else{
res[i][0] = stack.peek();
}
stack.push(i);
}
while(!stack.isEmpty()){
res[stack.pop()][1] = -1;
}
return res;
}
}
发表于 2022-09-13 19:24:51
回复(0)
public class Solution {
public int[][] foundMonotoneStack (int[] nums) {
//由于本体存在重复值，需要使用双向链表存放相同值
Stack<LinkedList<Integer>> stack = new Stack<>();
//存放结果的数组
int result[][] = new int[nums.length][2];
//依次遍历nums中每一个元素，i为数组的下标
for(int i=0;i<nums.length;i++) {
//栈本身遵顼从小到大的单调原则，如果出现反例则陆续从栈中弹出元素直到符合原则
//弹出的元素即是需要处理的信息
while(!stack.isEmpty()&&nums[stack.peek().peekLast()]>nums[i]) {
//取出栈顶的链表，从尾部开始一次赋值
LinkedList<Integer> tmp = stack.pop();
while(!tmp.isEmpty()) {
int index = tmp.pollLast();
//如果弹出元素后栈为空则left值为-1.否则left的值为当前栈顶链表的尾元素的值
//right值为即将进入栈的元素，下标就是i
if(stack.isEmpty()) {
result[index][0]=-1;
result[index][1]=i;
}
else {
result[index][0]=stack.peek().peekLast();
result[index][1]=i;
}
}
}
//每遍历一个元素，相当于处理的是之前的元素，处理之后该元素仍需要入栈
//如果该元素的值和当前栈顶元素对应的值相等，则添加到一个链表中，否则创建一个新链表
if(!stack.isEmpty()&&nums[stack.peek().peekLast()]==nums[i]) {
stack.peek().addLast(i);
}
else {
LinkedList<Integer> res = new LinkedList<>();
res.addLast(i);
stack.add(res);
}
}
//此时所有的元素已经遍历完成，该添加进去的元素已经添加过了
//此时栈里剩下的元素都是符合单调栈原则从小到大排列的
//依次从栈顶弹出元素，right值为-1，left值为弹出后此时栈顶元素的链表尾部的下标
//情况与上面类似，只不过right值为-1，当栈弹空时left为-1
while(!stack.isEmpty()) {
LinkedList<Integer> tmp = stack.pop();
while(!tmp.isEmpty()) {
int index = tmp.pollLast();
if(stack.isEmpty()) {
result[index][0]=-1;
result[index][1]=-1;
}else {
result[index][0]=stack.peek().peekLast();
result[index][1]=-1;
}
}
}
return result;
}
}
感觉写的挺清楚的，就是挺繁琐的，耗时有点高
发表于 2022-08-22 20:09:05
回复(1)
问题信息
通过挑战的用户
查看代码-
2022-09-17 11:16:36 -
2022-09-14 23:23:38 -
2022-09-14 02:08:10 -
2022-09-13 19:22:05
-
2022-09-13 15:13:27
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
