给定一个长度为 
的可能含有重复值的数组 
，找到每一个位置 
左边最近的位置 
和右边最近的位置 
，
和 
比 
小。
请设计算法，返回一个二维数组，表示所有位置相应的信息。位置信息包括：两个数字 和 。如果不存在，则值为 -1，下标从 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)
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 {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @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)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int一维数组
* @return int二维数组
*/
public int[][] foundMonotoneStack (int[] nums) {
// write code here
Stack<Integer> stack = new Stack<>();
int[][] result = new int[nums.length][2];
stack.push(-1);
for(int i=0; i<nums.length; i++) {
while(stack.peek()!=-1 && nums[stack.peek()]>nums[i]) {
//因为比较的数字一定比栈顶元素小，所以这里可以设定每个栈顶元素的右边较小数
result[stack.peek()][1] = i;
stack.pop();
}
//上面while循环中条件必须是>，不能是>=，因为等于的情况不能把结果加入结果集，需要单独提出来讨论
//（如果与栈顶元素相等说明自己左边的最近较小数与栈顶元素左边较小数一样，如果不相等说明栈顶元素就是左边的最近较小数）。
if(stack.peek()!=-1 && nums[stack.peek()]==nums[i]) {
result[i][0] = result[stack.peek()][0];
}else {
result[i][0] = stack.peek();
}
stack.push(i);
}
//stack中剩余的说明这些数字右边都没有比自己小的数字（因为是单调递增栈），那么把他们的结果集里第二个数字设为-1
while(stack.peek()!=-1){
result[stack.pop()][1] = -1;
}
return result;
}
}
发表于 2022-04-04 17:56:42
回复(0)
public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int一维数组 * @return int二维数组 */ public int[][] foundMonotoneStack (int[] nums) { Deque<Integer> stack = new LinkedList<>(); stack.push(-1); int len = nums.length; int[][] res = new int[len][2]; for(int i = 0; i < len; i++){ while (stack.peek() != -1 && nums[stack.peek()] >= nums[i]){ stack.poll(); } res[i][0] = stack.peek(); stack.push(i); } stack.clear(); stack.push(-1); for(int i = len - 1; i >= 0; i--){ while (stack.peek() != -1 && nums[stack.peek()] >= nums[i]){ stack.poll(); } res[i][1] = stack.peek(); stack.push(i); } return res; } }
发表于 2022-03-07 20:34:57
回复(0)
public int[][] foundMonotoneStack (int[] nums) {
// write code here
//维持两个单调栈，一个从nums头到尾构建单调栈，一个从nums尾到头构建单调栈
Deque<Integer> stack = new LinkedList<>();
Deque<Integer> reStack = new LinkedList<>();
int[][] res = new int[nums.length][2];
stack.push(-1);
reStack.push(-1);
for (int i = 0, j = nums.length - 1; i < nums.length; i++, j--) {
int cur = nums[i], reCur = nums[j];
while (stack.peek() != -1 && nums[stack.peek()] >= nums[i]) {
stack.pop();
}
//添加左边
res[i][0] = stack.peek();
stack.push(i);
while (reStack.peek() != -1 && nums[reStack.peek()] >= nums[j]) {
reStack.pop();
}
//添加右边
res[j][1] = reStack.peek();
reStack.push(j);
}
return res;
}
发表于 2022-02-22 16:51:14
回复(1)
保持栈底往栈顶是单调递增的，在弹栈时生成信息
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)
import java.util.*;
//七刷，弹压栈找离某数最近的左右节点
public class Solution {
//
public int[][] foundMonotoneStack (int[] nums) {
// write code here
int len = nums.length;
// 返回的数组构造
int[][] ans = new int[len][2];
// 用栈保存
Stack<Integer> stack = new Stack<>();
// 从左往右，依次进行入栈，保存从左到右的升序的值
for(int i = 0; i < len; i++){
// 如果栈里面的值都比其大，就pop
while(!stack.isEmpty() && nums[stack.peek()] >= nums[i]) stack.pop();
// 栈空，说明nums[i]左边没有比他小的值
if(stack.isEmpty()){
ans[i][0] = -1;
} else {
// 如果有比他小的，那么栈中的第一个元素的值就是离他最近的
ans[i][0] = stack.peek();
}
stack.push(i);
}
// 思路跟上面的一样，从右往左，保存升序值
stack.clear();
for(int i = len - 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-10-02 10:24:27
回复(0)
public int[][] foundMonotoneStack (int[] nums) {
// write code here
int n = nums.length;
int[][] ans = new int[n][2];
for(int i=0;i<n;i++)
Arrays.fill(ans[i],-1);
Stack<int[]> s1 = new Stack();
Stack<int[]> s2 = new Stack();
for(int i=0;i<n;i++){
while(!s1.isEmpty() && s1.peek()[1]>nums[i]){
int x = s1.peek()[0],y = s1.peek()[1];
ans[x][1] = i;
s1.pop();
}
s1.push(new int[]{i,nums[i]});
while(!s2.isEmpty() && s2.peek()[1]>=nums[i]){
s2.pop();
}
if(s2.isEmpty()){
ans[i][0] = -1;
}
else{
ans[i][0] = s2.peek()[0];
}
s2.push(new int[]{i,nums[i]});
}
return ans;
}
发表于 2021-09-09 15:41:26
回复(0)
问题信息
通过挑战的用户
查看代码-
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号
