Create Maximum Number LeetCode solution in Java

1
class Solution {
2
  public int[] maxNumber(int[] nums1, int[] nums2, int k) {
3
    String ans = "";
4
    for (int i = Math.max(0, k - nums2.length);
5
        i <= Math.min(nums1.length, k);
6
        i++) { // try all possible lengths from each seq
7
      String one = solve(nums1, i); // find the best seq matching len of i
8
      String two = solve(nums2, k - i); // len of k-i
9
      StringBuilder sb = new StringBuilder();
10
      int a = 0, b = 0;
11
      while (a < i || b < k - i) { // merge it to the max
12
        sb.append(
13
            one.substring(a).compareTo(two.substring(b)) >= 0 ? one.charAt(a++) : two.charAt(b++));
14
      }
15
      if (sb.toString().compareTo(ans) > 0) { // if better, we replace.
16
        ans = sb.toString();
17
      }
18
    }
19
    int[] res = new int[k];
20
    for (int i = 0; i < k; ++i) {
21
      res[i] = ans.charAt(i) - '0';
22
    }
23
    return res;
24
  }
25

26
  private String solve(int[] arr, int k) {
27
    Deque<Integer> stack = new ArrayDeque<>();
28
    for (int i = 0; i < arr.length; ++i) {
29
      while (!stack.isEmpty() && arr.length - i + stack.size() > k && stack.peek() < arr[i]) {
30
        stack.pop();
31
      }
32
      stack.push(arr[i]);
33
    }
34
    StringBuilder sb = new StringBuilder();
35
    for (int i = 0; i < k; i++) {
36
      sb.append(stack.pollLast());
37
    }
38
    return sb.toString();
39
  }
40
}