681. Next Closest Time

Given a time represented in the format "HH:MM", form the next closest time by reusing the current digits. There is no limit on how many times a digit can be reused.

You may assume the given input string is always valid. For example, "01:34", "12:09" are all valid. "1:34", "12:9" are all invalid.

Example 1:

Input: "19:34"
Output: "19:39"
Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later. It is not 19:33, because this occurs 23 hours and 59 minutes later.
Example 2:

Input: "23:59"
Output: "22:22"
Explanation: The next closest time choosing from digits 2, 3, 5, 9, is 22:22. It may be assumed that the returned time is next day's time since it is smaller than the input time numerically.

Solution

字符串模拟题,找出相应规律:
找到第一个比当前位置大的数,如果合法,赋值,并将后面的数置为最小值
类似next permutation

Complexity

Worst Time: O(N2)
O(N)

Code

class Solution {
    public String nextClosestTime(String time) {
        char[] digits = new char[]{time.charAt(0), time.charAt(1), time.charAt(3), time.charAt(4)};
        char[] sortedDigits = digits.clone();
        Arrays.sort(sortedDigits);
        int i = digits.length - 1;
        for(; i >= 0; i--){
            int j = 0;
            while(j < sortedDigits.length && sortedDigits[j] <= digits[i]) j++;;
            if(j < sortedDigits.length){
                char tmp = digits[i];
                digits[i] = sortedDigits[j];
                int hour = (digits[0] - '0') * 10 + (digits[1] - '0');
                int minute = (digits[2] - '0') * 10 + (digits[3] - '0');
                if(hour <= 24 && minute <= 60)
                    break;
                digits[i] = tmp; 
            }
        }
        for(int k = i + 1; k < digits.length; k++){
            digits[k] = sortedDigits[0];
        }
        
        StringBuilder sb = new StringBuilder();
        sb.append(digits[0]).append(digits[1]).append(":").append(digits[2]).append(digits[3]);
        return sb.toString();
    }
}