如何证明贪心决策原排序数组中每位选择的正确性？

本文共计2246个文字，预计阅读时间需要9分钟。

题目描述：这是LeetCode上的1846题，题目为减小和重新排列数组的最大元素。难度为中等。Tag：贪心给你一个正整数数组arr。请你对arr执行一些操作（也可以不执行任何操作），使得数组的每个元素都不大于它前面（或后面）的元素。返回你可以使arr满足这个条件的最大元素。示例：输入：arr=[1,2,3,4,5]输出：1解释：数组已经满足题目要求，所以返回1。输入：arr=[1,2,3,4,5,6]输出：1解释：对数组执行以下操作：- 将arr[5]改为1，得到[1,2,3,4,1,1]。- 将arr[4]改为1，得到[1,2,3,1,1,1]。- 将arr[3]改为1，得到[1,2,1,1,1,1]。- 将arr[2]改为1，得到[1,1,1,1,1,1]。- 将arr[1]改为1，得到[1,1,1,1,1,1]。- 将arr[0]改为1，得到[1,1,1,1,1,1]。最终数组满足题目要求，所以返回1。

题目描述

这是 LeetCode 上的 1846. 减小和重新排列数组后的最大元素 ，难度为 中等。

Tag : 「贪心」

给你一个正整数数组arr。请你对 arr执行一些操作（也可以不进行任何操作），使得数组满足以下条件：

• arr中 第一个元素必须为1。
• 任意相邻两个元素的差的绝对值 小于等于1，也就是说，对于任意的 1 <= i < arr.length（数组下标从 0 开始），都满足abs(arr[i] - arr[i - 1]) <= 1。abs(x)为x的绝对值。