贪心 - 单调性 - 《算法》

用排序法常见的情况是输入一个包含几个（一般一到两个）权值的数组，通过排序然后遍历模拟计算的方法求出最优值。

179. 最大数

/**
 * @param {number[]} nums
 * @return {string}
 */
var largestNumber = function(nums) {
  let r = nums.map(p => '' + p);
  r.sort((a, b) => {
    // 以拼接后的数值大小排序
    return Number(b + a) - Number(a + b);
  });
  r = r.join('');
  // 去除前缀0
  let i = 0;
  while (r[i] === '0') {
    i += 1;
  }
  r = r.substr(i);
  return r.length ? r : '0';
};

1833. 雪糕的最大数量

/**
 * @param {number[]} costs
 * @param {number} coins
 * @return {number}
 */
var maxIceCream = function(costs, coins) {
  costs.sort((a, b) => a - b);
  let t = 0, ans = 0;
  for (let i = 0; i < costs.length; i++) {
    if (t + costs[i] > coins) {
      break;
    }
    t += costs[i];
    ans++;
  }
  return ans;
};

334. 递增的三元子序列

难度中等346收藏分享切换为英文接收动态反馈
给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。

示例 1：
输入：nums = [1,2,3,4,5] 输出：true 解释：任何 i < j < k 的三元组都满足题意
示例 2：
输入：nums = [5,4,3,2,1] 输出：false 解释：不存在满足题意的三元组
示例 3：
输入：nums = [2,1,5,0,4,6] 输出：true 解释：三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6

提示：

1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1

进阶：你能实现时间复杂度为 O(n) ，空间复杂度为 O(1) 的解决方案吗？

思路：

贪心 + 单调栈（隐式，只需要两个下标，min和mid表示前面两个小的元素，有遇到更小的，就更新，这个策略是贪心选择）
i,j,k 三个数字是严格单调升序的，则必然最小的i 比较过程中笑了俩次，j比较中小了一次，且i 是最早出现的，后面的j、k出现时，满足比i大，同理，
k出现时，比j大。则设计两个下标min，mid代表i，j。每次先与min比较，小，则更新min，再与mid比较，小则更新mid，大说明已经找到满足条件的结果。

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var increasingTriplet = function(nums) {
  if (nums.length < 3) return false;
  let min = Number.MAX_SAFE_INTEGER;
  let mid = Number.MAX_SAFE_INTEGER;
  let r = 0;
  while (r < nums.length) {
    let n = nums[r++];
    if (n <= min) {
      min = n;
    } else if (n <= mid) {
      mid = n;
    } else if (n > mid) {
      return true;
    }
  }
  return false;
};

300. 最长递增子序列

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function (nums) {
  let p = [], ans = 0;
  for (let num of nums) {
    let i = 0, j = ans;

    // 二分查找右边界，然后更新数据。
    while (i < j) {
      let m = i + (( j - i) >>> 1);
      if (p[m] < num) {
        i = m + 1;
      } else {
        j = m;
      }
    }
    p[i] = num;
    // 若最后的位置j和ans一样，说明发现一个更长的。
    if (ans === j) ans++;
  }
  return ans;
};

// c++,另外一个写法，要使用ifelse 来判断，其实都是寻找可以插入num的右边界。
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len = 1, n = (int)nums.size();
        if (n == 0) {
            return 0;
        }
        vector<int> d(n + 1, 0);
        d[len] = nums[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i] > d[len]) {
                d[++len] = nums[i];
            } else {
                int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (d[mid] < nums[i]) {
                        pos = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                d[pos + 1] = nums[i];
            }
        }
        return len;
    }
};

581. 最短无序连续子数组

思路：单调栈，分别找到左右两个边界，左边界最小下标，右边界最大下标。

/**
 * @param {number[]} nums
 * @return {number}
 */
var findUnsortedSubarray = function(nums) {
  let s =  [], len = nums.length, left = len, right = 0;
  for (let i = 0; i < len; i++) {
    while (s.length && nums[s[s.length - 1]] > nums[i]) {
      left = Math.min(left, s.pop());
    }
    s.push(i);
  }
  if (left === len) return 0;

  s.length = 0;
  for (let i = len - 1; i >= 0; i--) {
    while (s.length && nums[s[s.length - 1]] < nums[i]) {
      right = Math.max(right, s.pop());
    }
    s.push(i);
  }
  if (right === 0) return 0;
  return right - left + 1;
};

402. 移掉 K 位数字

思路：单调栈，保持单调递增栈，
代码实现的要点：
1、在删除数字时计数；
2、若遍历后，k不为0，则从栈中弹出剩余的k个数字。
3、删除前缀0

/**
 * @param {string} num
 * @param {number} k
 * @return {string}
 */
var removeKdigits = function(num, k) {
  if (num.length <= k) {
    return '0';
  }
  const s = [num[0]];
  for (let i = 1; i < num.length; i++) {
    while (k && s[s.length - 1] > num[i]) {
      k -= 1;
      s.pop();
    }
    s.push(num[i]);
  }
  while (k) {
    s.pop();
    k -= 1;
  }
  while (s[0] === '0') {
    s.shift();
  }
  return s.length ? s.join('') : '0';
};

376. 摆动序列

思路：峰谷分别为连续序列的极大值和极小值，求极大和极小的快点的两个思路：

1、二阶导数为0，
2、一阶导数的前后符号相反。

这里是离散的序列，所以用第二种方式更加方便计算。

定义pre为前一个一阶导数，由于序列的索引为单位变量1，所以使用连续的两个数值的差值来代表一阶导数。

故满足条件的极大值和极小值，需要确保pre和current符号相反。
初始化：pre = nums[1] - nums[0, ans = pre !== 0 ? 2 : 1;
循环：i in [2, len)
if (pre >= 0 && current < 0 || pre <= 0 && current > 0) { ans ++; pre = current;}

/**
 * @param {number[]} nums
 * @return {number}
 */
var wiggleMaxLength = function(nums) {
  if (nums.length === 1) {
    return 1;
  }
  let pre = nums[1] - nums[0];
  let ans = pre !== 0 ? 2 : 1;
  for (let i = 2; i < nums.length; i++) {
    const current = nums[i] - nums[i-1];
    const flag = (pre >= 0 && current < 0) || (pre <= 0 && current > 0);
    if (flag) {
      ans +=  1;
      pre = current;
    }
  }
  return ans;  
};

1713. 得到子序列的最少操作次数

/**
 * @param {number[]} target
 * @param {number[]} arr
 * @return {number}
 */
var minOperations = function(target, arr) {
  const mp = new Map();
  for (let i = 0; i < target.length; i++) {
    mp.set(target[i], i);
  }
  // 如下为LIS的O(nlogN)复杂度的算法。
  let p = [], ans = 0;
  for (let k = 0; k < arr.length; k++) {
    let n = arr[k];
    if (!mp.has(n)) continue;
    let pos = mp.get(n);
    let i = 0, j = ans;
    while ( i < j) {
      let m = i + ((j - i) >>> 1);
      if (p[m] < pos) {
        i = m + 1;
      } else {
        j = m;
      }
    }
    p[i] = pos;
    if (ans === j) ans++;
  }
  return target.length - ans;
};

406. 根据身高重建队列

思路：k具有单调性，所以排序时要考虑k的大小顺序，为了能够找到正确的位置，身高降序，这样后面身高较小的数字前移时，不会改变大小关系。

按身高降序，k升序排序，然后检查后面的数组，并插入到正确的位置，位置信息来源与k，因为是按照升高降序的，所以后面的数据前移到k位置后，正好是满足要求的位置。

/**
 * @param {number[][]} people
 * @return {number[][]}
 */
var reconstructQueue = (people) => {
  const arrs = people.sort(childrenComparator);
  const r = [];
  for (let i = 0; i < arrs.length; i++) {
    r.splice(arrs[i][1], 0, arrs[i]);
  }
  return r;
};

function childrenComparator(left, right) {
  if (left[0] === right[0]) {
    return left[1] - right[1];
  }
  return right[0] - left[0];
}

122. 买卖股票的最佳时机 II

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
  let sum = 0;
  for (let i = 1; i < prices.length; i++) {
    if (prices[i] > prices[i-1]) {
      sum += prices[i] - prices[i-1];
    }
  }
  return sum;
};

714. 买卖股票的最佳时机含手续费

/**
 * @param {number[]} prices
 * @param {number} fee
 * @return {number}
 */
var maxProfit = function(prices, fee) {
  let len = prices.length, profit = 0, buy = prices[0] + fee;
  for (let i = 1; i < len; i++) {
    if (prices[i] + fee < buy) {
      buy = prices[i] + fee;
    } else if (prices[i] > buy) {
      profit += prices[i] - buy;
      buy = prices[i];
    }
  }
  return profit;
};

/**
 * @param {number[]} prices
 * @param {number} fee
 * @return {number}
 */
var maxProfit = function(prices, fee) {
  let up = 0, down = -prices[0];
  for (let i = 1; i < prices.length; i++) {
    up = Math.max(up, down + prices[i] - fee);
    down = Math.max(down, up - prices[i]);
  }
  return Math.max(up, down);
};

1710. 卡车上的最大单元数

请你将一些箱子装在一辆卡车上。给你一个二维数组 boxTypes ，其中 boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi] ：

numberOfBoxesi 是类型 i 的箱子的数量。
numberOfUnitsPerBoxi 是类型 i 每个箱子可以装载的单元数量。
整数 truckSize 表示卡车上可以装载箱子的最大数量。只要箱子数量不超过 truckSize ，你就可以选择任意箱子装到卡车上。

返回卡车可以装载单元的最大总数。

示例 1：

输入：boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
输出：8
解释：箱子的情况如下：

1 个第一类的箱子，里面含 3 个单元。
2 个第二类的箱子，每个里面含 2 个单元。
3 个第三类的箱子，每个里面含 1 个单元。
可以选择第一类和第二类的所有箱子，以及第三类的一个箱子。
单元总数 = (1 3) + (2 2) + (1 * 1) = 8
示例 2：

输入：boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
输出：91

提示：

1 <= boxTypes.length <= 1000
1 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000
1 <= truckSize <= 106

思路：按照每个盒子的单元数降序排序，然后进行贪心选择累加即可，注意不能超过箱子的上限。由此，可以计算结果集。

/**
 * @param {number[][]} boxTypes
 * @param {number} truckSize
 * @return {number}
 */
var maximumUnits = function(boxTypes, truckSize) {
  let sum = 0, boxSum = 0;
  boxTypes.sort((a, b) => b[1] - a[1]);
  for (let i = 0; i < boxTypes.length; i += 1) {
    let s = 0;
    while (s <= boxTypes[i][0] && boxSum + s <= truckSize) {
      s += 1;
    }
    boxSum += (s-1);
    sum += (s-1) * boxTypes[i][1];
  }
  return sum;
};

1029. 两地调度

难度中等208收藏分享切换为英文接收动态反馈
公司计划面试 2n 人。给你一个数组 costs ，其中 costs[i] = [aCosti, bCosti] 。第 i 人飞往 a 市的费用为 aCosti ，飞往 b 市的费用为 bCosti 。
返回将每个人都飞到 a 、b 中某座城市的最低费用，要求每个城市都有 n 人抵达。

示例 1：
输入：costs = [[10,20],[30,200],[400,50],[30,20]] 输出：110 解释： 第一个人去 a 市，费用为 10。第二个人去 a 市，费用为 30。第三个人去 b 市，费用为 50。第四个人去 b 市，费用为 20。最低总费用为 10 + 30 + 50 + 20 = 110，每个城市都有一半的人在面试。
示例 2：
输入：costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]] 输出：1859
示例 3：
输入：costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]] 输出：3086

提示：

2 * n == costs.length
2 <= costs.length <= 100
costs.length 为偶数
1 <= aCosti, bCosti <= 1000

/**
 * @param {number[][]} costs
 * @return {number}
 */
var twoCitySchedCost = function(costs) {
  costs.sort((a, b) => a[0] - a[1] - (b[0] - b[1]));
  let sum = 0, len = costs.length/2;
  for (let i = 0; i < len; i++) {
    sum += costs[i][0] + costs[i + len][1];
  }
  return sum;
};

135. 分发糖果

/**
 * @param {number[]} ratings
 * @return {number}
 */
var candy = function(ratings) {
  const len = ratings.length;
  const lefts = new Array(len).fill(1);
  // 从左向右寻找，left 数组元素++ 递增
  for (let i = 1; i < len; i++) {
    if (ratings[i] > ratings[i-1]) {
      lefts[i] = lefts[i-1] + 1;
    }
  }
  let sum = lefts[len - 1];
  // 从右向左寻找，如果与lefts的单调性相反，则更新left数组。
  for (let i = len - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i+1] && lefts[i] <= lefts[i+1]) {
      lefts[i] = lefts[i+1] + 1;
    }
    // 更新累加和。
    sum += lefts[i];
  }
  return sum;
};

738. 单调递增的数字

难度中等203收藏分享切换为英文接收动态反馈
给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）
示例 1:
输入: N = 10
输出: 9
示例 2:
输入: N = 1234
输出: 1234
示例 3:
输入: N = 332
输出: 299
说明: N 是在 [0, 10^9] 范围内的一个整数。

/**
 * @param {number} n
 * @return {number}
 */
var monotoneIncreasingDigits = function(n) {
  let res = 0;
  // 倍数
  let seed = 1;
  while (n > 0) { // 从右向左遍历
      let num = n % 10;
      n = (n - num)/10;
      let high = n % 10;
      if (high > num) {
          // 高位大于低位，舍去低位，高位数字 - 1， 将低位全部置为9。
          res = seed*10 - 1;
          n -= 1;
      }else  {
          res = num * seed + res;
      }
      seed *= 10;
  }
  return res
};

class Solution:
    def monotoneIncreasingDigits(self, N: int) -> int:
        ones = 111111111
        result = 0
        for _ in range(9):
            while result + ones > N:
                ones //= 10
            result += ones
        return result

var monotoneIncreasingDigits = function(n) {
    const strN = n.toString().split('').map(v => +v);
    let i = 1;
    while (i < strN.length && strN[i - 1] <= strN[i]) {
        i += 1;
    }
    if (i < strN.length) {
        while (i > 0 && strN[i - 1] > strN[i]) {
            strN[i - 1] -= 1;
            i -= 1;
        }
        for (i += 1; i < strN.length; ++i) {
            strN[i] = 9;
        }
    }
    return parseInt(strN.join(''));
};

826. 安排工作以达到最大收益

/**
 * @param {number[]} difficulty
 * @param {number[]} profit
 * @param {number[]} worker
 * @return {number}
 */
var maxProfitAssignment = function(difficulty, profit, worker) {
  const prices = [];
  for (let i = 0; i < difficulty.length; i++) {
    prices.push([difficulty[i], profit[i]]);
  }
  prices.sort((a, b) => b[1] - a[1]);
  // worker.sort((a, b) => a - b);
  let ans = 0;
  for (let i = 0; i < worker.length; i++) {
    let j = 0;
    while (j < prices.length && prices[j][0] > worker[i]) {
      j++;
    }
    if (j < prices.length) {
      ans += prices[j][1];
    }
  }
  return ans;
};

945. 使数组唯一的最小增量

/**
 * @param {number[]} nums
 * @return {number}
 */
var minIncrementForUnique = function(nums) {
  nums.sort((a, b) => a-b);
  let top = nums[0], ans = 0;
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] <= top) {
      ans += top + 1 -  nums[i];
    }
    top = Math.max(top + 1, nums[i]);
  }
  return ans;
};

1053. 交换一次的先前排列

/**
 * @param {number[]} arr
 * @return {number[]}
 */
var prevPermOpt1 = function(arr) {
  for (let i = arr.length - 2 ; i >= 0 ; i--) {
    if (arr[i] > arr[i+1]) {
      let max = i + 1;
      for (let j = i + 1; j < arr.length; j++) {
        if (arr[i] > arr[j] && arr[j] > arr[max]) {
          max = j;
        }
      }
      if (max < arr.length) {
        [arr[max], arr[i]] = [arr[i], arr[max]];
        // const temp = arr[max];
        // arr[max] = arr[i];
        // arr[i] = temp;
        break;
      }
    }
  }
  return arr;
};

/**
 * @param {number[]} arr
 * @return {number[]}
 */
var prevPermOpt1 = function(arr) {
  let left = 0, right = 0;
  for (let i = 0 ; i < arr.length - 1 ; i++) {
    if (arr[i] > arr[i+1]) {
      left = i;
      right = i + 1;
    } else if (arr[i] < arr[i + 1] && arr[left] > arr[i + 1]) {
      right = i + 1;
    }
  }
  [arr[left], arr[right]] = [arr[right], arr[left]];
  return arr;
};