河南海绵城市建设网站,大新网站制作,娱乐网站制作,网站建设营销公司给你一个数组 seats 表示一排座位#xff0c;其中 seats[i] 1 代表有人坐在第 i 个座位上#xff0c;seats[i] 0 代表座位 i 上是空的#xff08;下标从 0 开始#xff09;。
至少有一个空座位#xff0c;且至少有一人已经坐在座位上。
亚历克斯希望坐在一个能够使他与…给你一个数组 seats 表示一排座位其中 seats[i] 1 代表有人坐在第 i 个座位上seats[i] 0 代表座位 i 上是空的下标从 0 开始。
至少有一个空座位且至少有一人已经坐在座位上。
亚历克斯希望坐在一个能够使他与离他最近的人之间的距离达到最大化的座位上。
返回他到离他最近的人的最大距离。
示例 1
输入seats [1,0,0,0,1,0,1] 输出2 解释 如果亚历克斯坐在第二个空位seats[2]上他到离他最近的人的距离为 2 。 如果亚历克斯坐在其它任何一个空位上他到离他最近的人的距离为 1 。 因此他到离他最近的人的最大距离是 2 。 示例 2
输入seats [1,0,0,0] 输出3 解释 如果亚历克斯坐在最后一个座位上他离最近的人有 3 个座位远。 这是可能的最大距离所以答案是 3 。 示例 3
输入seats [0,1] 输出1
提示
2 seats.length 2 * 104seats[i] 为 0 或 1至少有一个 空座位至少有一个 座位上有人
/*** param {number[]} seats* return {number}*/
var maxDistToClosest function (seats) {let max 0let j 0let len 0for (let i 0; i seats.length; i) {if (seats[i] 1) {if (seats[j] 0) {len i - jmax Math.max(len, max)j i} else if (seats[j] 1) {len Math.floor((i - j) / 2)max Math.max(len, max)j i}}if (i seats.length - 1 seats[i] 0) {len i - jmax Math.max(len, max)}}return max
};解题思路https://leetcode.cn/problems/maximize-distance-to-closest-person/solutions/2393766/dao-zui-jin-de-ren-de-zui-da-ju-chi-by-l-zboe/
方法一双指针 贪心 思路与算法
题目给出一个下标从 0 开始长度为 n 的数组 seats其中 seats[i]1 表示有人坐在第 i 个位置上在该题解中我们称之为「有人座位」seats[i]0 表示第 i 个座位为空称之为「无人座位」并且题目数据保证至少有一个「有人座位」和「无人座位」。现在我们需要找到一个「无人座位」使得该位置与距离该位置最近的「有人位置」之间的距离最大并返回该值。
首先假设已经确定了我们所选择的「无人座位」i 的左和右离它最近的「有人座位」分别为座位 l 和 r0≤lirn。那么此时座位 i 的离其位置最近的人的距离 其中当 i⌊ (lr)/2 ⌋ 时取到等号。所以对于两个相邻的「有人座位」我们在中间就坐一定是最优的。因此我们可以用「双指针」来找到每一对相邻的有人座位并计算若在其中间就坐能得到的最大间隔距离。
以上的讨论是建立在我们选择的「无人座位」的左右都存在「有人座位」的情况。对于边缘的「无人座位」即其某一侧不存在「有人座位」
若左边存在边缘的「无人座位」则此时为了使距离其最近的右边的「有人座位」最远我们应该尽可能的往左边坐即坐在第一个位置。若右边存在边缘的「无人座位」则此时为了使距离其最近的左边的「有人座位」最远我们应该尽可能的往右边坐即坐在第最后一个位置。
最后返回全部情况中能得到的最大距离即可。
leetcodehttps://leetcode.cn/problems/maximize-distance-to-closest-person/description/
