暴力解O(n^2)，因此最优解应该是Onlogn，或者On，但是大概率猜测是nlogn。
class Solution {
public List<Integer> countSmaller(int[] nums) {
Deque<Integer> stack = new LinkedList<>();
Deque<Integer> stack1 = new LinkedList<>();
List<Integer> res = new ArrayList<>();
for (int i = nums.length - 1; i >= 0; i--) {
if (i == nums.length - 1) {
res.add(0);
stack.offerFirst(nums[i]);
} else {
while (!stack.isEmpty() && stack.peek() >= nums[i]) {
stack1.offerFirst(stack.pollFirst());
}
res.add(0, stack.size());
stack.offerFirst(nums[i]);
while (!stack1.isEmpty()) {
stack.offerFirst(stack1.pollFirst());
}
}
}
return res;
}
}
这是第一个犯的错是选择了单向栈，但是没有考虑清，如果是一个递增数列，时间复杂的依然是n^2
正解，mergeSort，时间复杂度O(nlogn)
class Solution {
int[] count;
public List<Integer> countSmaller(int[] nums) {
List<Integer> res = new ArrayList<Integer>();
count = new int[nums.length];
int[] indexes = new int[nums.length];
for(int i = 0; i < nums.length; i++){
indexes[i] = i;
}
mergesort(nums, indexes, 0, nums.length - 1);
for(int i = 0; i < count.length; i++){
res.add(count[i]);
}
return res;
}
private void mergesort(int[] nums, int[] indexes, int start, int end){
if(end <= start){
return;
}
int mid = (start + end) / 2;
mergesort(nums, indexes, start, mid);
mergesort(nums, indexes, mid + 1, end);
merge(nums, indexes, start, end);
}
private void merge(int[] nums, int[] indexes, int start, int end){
int mid = (start + end) / 2;
int left_index = start;
int right_index = mid+1;
int rightcount = 0;
int[] new_indexes = new int[end - start + 1];
int sort_index = 0;
while(left_index <= mid && right_index <= end){
if(nums[indexes[right_index]] < nums[indexes[left_index]]){
new_indexes[sort_index] = indexes[right_index];
rightcount++;
right_index++;
}else{
new_indexes[sort_index] = indexes[left_index];
count[indexes[left_index]] += rightcount;
left_index++;
}
sort_index++;
}
while(left_index <= mid){
new_indexes[sort_index] = indexes[left_index];
count[indexes[left_index]] += rightcount;
left_index++;
sort_index++;
}
while(right_index <= end){
new_indexes[sort_index++] = indexes[right_index++];
}
for(int i = start; i <= end; i++){
indexes[i] = new_indexes[i - start];
}
}
}
