利用单调栈思路解决递增关系数据问题

• 一、题目描述
• 二、解题思路
• • 思路1：
  • 思路2：
• 三、代码实现
• • 1：暴力法
  • 2：单调栈

一、题目描述

在对数据进行排序的过程中，通常采用取1个数作为主元，通过比较交换，把比主元小的数挪到它左边；把比主元大的元素挪到右边。现给定一个划分后的正整数序列，请问有多少个元素可能是排序过程中选中的主元？并按顺序输出这些值。
举例
[1,3,2,4,5]
输出
[1,4,5]

二、解题思路

思路1：

通过暴力解法，分别比较每个数的左边和右边值，如果当前值大于左边值且当前值小于右边值，则保存此值到列表中，最后对列表排序输出。

思路2：

由于满足主元的条件：其右边值一定大于它，其左边值一定小于它，相当于有一个隐藏的递增关系，可以考虑单调栈，此解法更加高效。单调栈算法思路题

三、代码实现

1：暴力法

// 暴力法，先比较左边的最大值，再比较右边的最大值，如果当前值比左边大，比右边小，则满足
public static int[] majorityNumber2(int[] nums) {
List<Integer> list = new ArrayList<>();
list.add(nums[0]);
for (int i = 1; i < nums.length; i++) {
boolean left = checkLeft(0, i, nums[i], nums);
boolean right = checkRight(i, nums.length, nums[i], nums);
if (left && right) {
list.add(nums[i]);
}
}
int[] array = list.stream().mapToInt(Integer::valueOf).toArray();
Arrays.sort(array);
return array;
}
private static boolean checkLeft(int start, int end, int num, int[] numbers) {
int i = 0;
while (i < end) {
if (numbers[i] < num) {
i++;
} else {
break;
}
}
return i == end;
}
private static boolean checkRight(int start, int end, int num, int[] numbers) {
int i = start;
while (i < end) {
if (numbers[i] >= num) {
i++;
} else {
break;
}
}
return i == end;
}

2：单调栈

// 利用单调栈解决递增问题
public static int[] majorityNumber(int[] nums) {
Deque<Integer> stack = new ArrayDeque<>();
int max = Integer.MAX_VALUE;
stack.push(nums[0]);
for (int i = 1; i < nums.length; i++) {
if (nums[i] < max && !stack.isEmpty() && max == stack.peek()) {
// 如果当前值小于栈顶，且小于已经比较过的最大值，则出栈
stack.pop();
} else if (nums[i] >= stack.peek()) {
// 如果当前值大于栈顶，则入栈，并更新已经比较过的元素中的最大值
stack.push(nums[i]);
max = nums[i];
}
// 需要通过while循环，将栈顶大于当前值的元素出栈，保证“右边值大于左边”
while (!stack.isEmpty() && nums[i] < stack.peek()) {
stack.pop();
}
}
int[] result = stack.stream().mapToInt(Integer::valueOf).toArray();
Arrays.sort(result);
return result;
}在这里插入代码片