0798. Smallest Rotation with Highest Score

题目信息

题号:

0798

难度:

Hard

主题:

数组、循环旋转、评分

原题:

LeetCode 0798

重点:

旋转 k 表示把原下标 k 处元素移到新数组开头;旋转后元素值不大于其新下标便得一分,需返回最高分对应的最小 k

题目重述

给定长度为 n 的整数数组 nums。选择整数 k,其中 0 <= k < n,将数组向左循环旋转 k 个位置,结果为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], ..., nums[k-1]]。

旋转后,对每个下标 i,若该位置的元素满足 nums_rotated[i] <= i,则获得 1 分。一次旋转的总分是所有满足条件位置的数量。

请返回能够取得最高分的旋转量 k;若多个 k 的得分并列最高,返回其中最小的一个。

1 <= n <= 10^5,0 <= nums[i] < n。

自建示例

最高分出现并列时选择较小旋转量:

输入:nums = [1,0,3,2]
输出:1
解释:k = 0、1、2、3 时的得分依次为 2、3、2、3。最高分 3 同时由 k = 1 和 k = 3 获得,因此返回较小的 1。

数组只有一个元素:

输入:nums = [0]
输出:0
解释:长度为 1 时只允许选择旋转量 0。旋转后元素 0 位于下标 0,满足 ``0 <= 0`` 并获得一分,因此唯一可选的 0 也是答案。