376. 摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

  • 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
  • 相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

示例 1：
输入：nums = [1,7,4,9,2,5] 输出：6 解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。
示例 2：
输入：nums = [1,17,5,10,13,15,10,5,16,8] 输出：7 解释：这个序列包含几个长度为 7 摆动序列。 其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。
示例 3：
输入：nums = [1,2,3,4,5,6,7,8,9] 输出：2

提示：

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

进阶：你能否用 O(n) 时间复杂度完成此题?

思路：
贪心，选所有的局部极值点
证明：离散化的费马引理，除首尾外最优解的元素个数不会超过局部极值点的总数，而我们选取了所有极值点，其个数大于等于最优解元素个数，又因为贪心的方法找到的元素数一定小于等于最优解，故贪心解是最优解

  1. class Solution {
  2.     public int wiggleMaxLength(int[] nums) {
  3.         int n = nums.length;
  5.         int cnt = 1;
  6.         int pre = 0;
  7.         for (int i = 1; i < n ; i++) {
  8.             int x = nums[i] - nums[i - 1];
  9.             if ((pre == 0 && x != 0) || (pre > 0 && x < 0) || (pre < 0 && x > 0)) {
  10.                 pre = x;
  11.                 cnt++;
  12.             }
  13.         }
  14.         return cnt;
  15.     }
  16. }

324. 摆动排序 II

给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]… 的顺序。
你可以假设所有输入数组都可以得到满足题目要求的结果。

示例 1：
输入：nums = [1,5,1,1,6,4] 输出：[1,6,1,5,1,4] 解释：[1,4,1,5,1,6] 同样是符合题目要求的结果，可以被判题程序接受。
示例 2：
输入：nums = [1,3,2,2,3,1] 输出：[2,3,1,3,1,2]

提示：

  • 1 <= nums.length <= 5 * 104
  • 0 <= nums[i] <= 5000
  • 题目数据保证，对于给定的输入 nums ，总能产生满足题目要求的结果

进阶：你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？

思路：
如何构造？
排序
将排序后的中位数尽可能分开
不能先放偶数下标，再放奇数下标，对应原数组中的下标递增
例如：4 5 5 6放完后是4 5 5 6不满足要求
必须先放奇数下标，再放偶数下标，对应原数组中的下标递减
例如：4 5 5 6放完后是5 6 4 5满足要求

  1. class Solution {
  2.     public void wiggleSort(int[] nums) {
  3.         int n = nums.length;
  4.         int[] a = new int[n];
  5.         for (int i = 0; i < n; i++)
  6.             a[i] = nums[i];
  7.         Arrays.sort(a);
  9.         int j = n - 1;
  10.         for (int i = 1; i < n; i += 2) {
  11.             nums[i] = a[j];
  12.             j--;
  13.         }
  14.         for (int i = 0; i < n; i += 2) {
  15.             nums[i] = a[j];
  16.             j--;
  17.         }
  18.     }
  19. }

如何优化 ？
第k大数(快速选择) + 三数排序 + 映射 + 构造
A[i] = (2 * i + 1) % (n | 1)
例：可将0 1 2 3 4 5 6映射到1 3 5 0 2 4 6
找到第n / 2大数，以此为依据进行三数排序(倒排)，根据映射关系放到对应位置构造出目标结果

  1. class Solution {
  2.     int n;
  3.     public void wiggleSort(int[] nums) {
  4.         n = nums.length;
  5.         int mid = quickSort(nums, 0, n - 1, n / 2);
  6.         // System.out.println(mid);
  7.         for (int i = 0, l = 0, r = n - 1; i <= r; ) {
  8.             if (nums[A(i)] > mid) {
  9.                 swap(nums, A(i), A(l));
  10.                 i++;
  11.                 l++;
  12.             } else if (nums[A(i)] < mid) {
  13.                 swap(nums, A(i), A(r));
  14.                 r--;
  15.             } else {
  16.                 i++;
  17.             }
  18.         }
  19.     }
  21.     int A(int x) {
  22.         return (2 * x + 1) % (n | 1);
  23.     }
  25.     int quickSort(int[] q, int l, int r, int k) {
  26.         if (l >= r)
  27.             return q[l];
  29.         int x = q[l + r >> 1], i = l - 1, j = r + 1;
  30.         while (i < j) {
  31.             while (q[++i] < x);
  32.             while (q[--j] > x);
  33.             if (i < j) {
  34.                 swap(q, i, j);
  35.             }
  36.         }
  38.         if (j >= k)
  39.             return quickSort(q, l, j, k);
  40.         else
  41.             return quickSort(q, j + 1, r, k);
  42.     }
  44.     void swap(int[] a, int i, int j) {
  45.         int t = a[i];
  46.         a[i] = a[j];
  47.         a[j] = t;
  48.     }
  49. }