798. Smallest Rotation with Highest Score Hard

1/**
2 * [798] Smallest Rotation with Highest Score
3 *
4 * You are given an array nums. You can rotate it by a non-negative integer k so that the array becomes [nums[k], nums[k + 1], ... nums[nums.length - 1], nums[0], nums[1], ..., nums[k-1]]. Afterward, any entries that are less than or equal to their index are worth one point.
5 * 
6 * 	For example, if we have nums = [2,4,1,3,0], and we rotate by k = 2, it becomes [1,3,0,2,4]. This is worth 3 points because 1 > 0 [no points], 3 > 1 [no points], 0 <= 2 [one point], 2 <= 3 [one point], 4 <= 4 [one point].
7 * 
8 * Return the rotation index k that corresponds to the highest score we can achieve if we rotated nums by it. If there are multiple answers, return the smallest such index k.
9 *  
10 * Example 1:
11 * 
12 * Input: nums = [2,3,1,4,0]
13 * Output: 3
14 * Explanation: Scores for each k are listed below: 
15 * k = 0,  nums = [2,3,1,4,0],    score 2
16 * k = 1,  nums = [3,1,4,0,2],    score 3
17 * k = 2,  nums = [1,4,0,2,3],    score 3
18 * k = 3,  nums = [4,0,2,3,1],    score 4
19 * k = 4,  nums = [0,2,3,1,4],    score 3
20 * So we should choose k = 3, which has the highest score.
21 * 
22 * Example 2:
23 * 
24 * Input: nums = [1,3,0,2,4]
25 * Output: 0
26 * Explanation: nums will always have 3 points no matter how it shifts.
27 * So we will choose the smallest k, which is 0.
28 * 
29 *  
30 * Constraints:
31 * 
32 * 	1 <= nums.length <= 10^5
33 * 	0 <= nums[i] < nums.length
34 * 
35 */
36pub struct Solution {}
37
38// problem: https://leetcode.com/problems/smallest-rotation-with-highest-score/
39// discuss: https://leetcode.com/problems/smallest-rotation-with-highest-score/discuss/?currentPage=1&orderBy=most_votes&query=
40
41// submission codes start here
42
43impl Solution {
44    pub fn best_rotation(nums: Vec<i32>) -> i32 {
45        0
46    }
47}
48
49// submission codes end
50
51#[cfg(test)]
52mod tests {
53    use super::*;
54
55    #[test]
56    fn test_798() {
57    }
58}
59