高度检查器
学校在拍年度纪念照时，一般要求学生按照 非递减 的高度顺序排列。
请你返回至少有多少个学生没有站在正确位置数量。该人数指的是：能让所有学生以 非递减 高度排列的必要移动人数。
示例：
输入：[1,1,4,2,1,3] 输出：3 解释： 高度为 4、3 和最后一个 1 的学生，没有站在正确的位置。
思路：先保存原来数组，然后对数组排序，比较不一致的结果
class Solution { public int heightChecker(int[] heights) { int[] newHeight = Arrays.copyOf(heights,heights.length); Arrays.sort(newHeight); int res = 0; for(int i=0; i<heights.length; i++){ if(newHeight[i]!=heights[i]) res++; } return res; } }
爱生气的书店老板 今天，书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客（customers[i]）会进入书店，所有这些顾客都会在那一分钟结束后离开。 在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。 当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的。 书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 X 分钟不生气，但却只能使用一次。 请你返回这一天营业下来，最多有多少客户能够感到满意的数量。 示例： 输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3 输出：16 解释： 书店老板在最后 3 分钟保持冷静。 感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.
思路：双指针变形，先统计出不生气时候的值，然后双指针内的窗口保持在X之内。具体作法为，当需要容忍的次数没有超过界限的时候，快指针往前滑动，总满意数增加；当超过的时候，慢指针所指向的需要依条件减少
class Solution { public int maxSatisfied(int[] customers, int[] grumpy, int X) { int now = 0; for(int i=0; i<customers.length; i++){ if(grumpy[i]==0) { now+=customers[i]; } } int res = now; for(int i=0, j=0; i<customers.length; i++){ now += grumpy[i]==1 ? customers[i] : 0; if(i>=X){ now -= grumpy[j]==1 ? customers[j] : 0; j++; } res = Math.max(now, res); } return res; } }
交换一次的先前排列
给你一个正整数的数组 A（其中的元素不一定完全不同），请你返回可在 一次交换（交换两数字 A[i] 和 A[j] 的位置）后得到的、按字典序排列小于 A 的最大可能排列。
如果无法这么操作，就请返回原数组。
示例 1：
输入：[3,2,1] 输出：[3,1,2] 解释： 交换 2 和 1
示例 2：
输入：[1,1,5] 输出：[1,1,5] 解释： 这已经是最小排列
示例 3：
输入：[3,1,1,3] 输出：[1,3,1,3] 解释： 交换 1 和 3
//（举一反三：用辅助栈对栈进行排序）本题只需要分析出，尽可能保证右侧有序即可。即如果发现右侧有不有序的情况下，重新排列。
class Solution { public int[] prevPermOpt1(int[] A) { Stack<Integer> stack = new Stack<>(); for(int i=A.length-1; i>=0; i--){ if(i==A.length-1 || A[i]<=A[i+1]){ stack.push(i); }else{ int pre=stack.pop(); while(!stack.isEmpty() && A[i]>A[stack.peek()]){ pre = stack.pop(); } int tmp = A[i]; A[i] = A[pre]; A[pre] = tmp; break; } } return A; } }
距离相等的条形码 在一个仓库里，有一排条形码，其中第 i 个条形码为 barcodes[i]。 请你重新排列这些条形码，使其中两个相邻的条形码 不能 相等。 你可以返回任何满足该要求的答案，此题保证存在答案。 示例 1： 输入：[1,1,1,2,2,2] 输出：[2,1,2,1,2,1] 示例 2： 输入：[1,1,1,1,2,2,3,3] 输出：[1,3,1,3,2,1,2,1]
//简化成用颜色对数组进行涂色，先统计出每个颜色的次数。然后用一个最大堆维护颜色和对应的次数。着色时，当然优先用频率最高的颜色。为了保证不碰撞，我们先从偶数位开始涂色，然后奇数位涂色。
class Solution { public int[] rearrangeBarcodes(int[] barcodes) { Map<Integer, Integer> map = new HashMap<>(); for(int barcode: barcodes){ map.put(barcode, map.getOrDefault(barcode, 0)+1); } final int len = barcodes.length; PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->b[1]-a[1]); for(Map.Entry<Integer, Integer> entry: map.entrySet()){ q.offer(new int[]{entry.getKey(), entry.getValue()}); } int[] now = q.poll(), res = new int[len]; for(int i=0; i<len; i+=2){ if(now[1]<=0){ now = q.poll(); } res[i] = now[0]; now[1] -= 1; } for(int i=1; i<len; i+=2){ if(now[1]<=0){ now = q.poll(); } res[i] = now[0]; now[1] -= 1; } return res; } }