l**o
发帖数: 356 | 1 给一个数组，比如【5，2，6，1】
对于5，它的右边有两个数字比它小；对于2，它的右边有一个比小；6的右边有1个比它
小；1的右边0个比它小.
返回2 1 1=4
有没有什么好方法呀？
谢谢 |
l********6
发帖数: 129 | 2 虽然没做过 但是目测复杂度也就是降到nlogn吧 不知道有没有大神能想出线性的解法
nlogn的话就从后往前遍历 用一个set存之前的那些数 然后拿到下一个数的时候 在set
里面找upperbound 然后得出upperbound前面有多少个数 再把这个数插到upperbound之
前 整体上相当于维护一颗bst（实际上是rbtree）
[在 lalo (lalo) 的大作中提到：]
：给一个数组，比如【5，2，6，1】
：对于5，它的右边有两个数字比它小；对于2，它的右边有一个比小；6的右边有1个比
它小；1的右边0个比它小.
：........... |
s***c
发帖数: 639 | 3 augmented tree,加个counter
【在 l**o 的大作中提到】
: 给一个数组，比如【5，2，6，1】
: 对于5，它的右边有两个数字比它小；对于2，它的右边有一个比小；6的右边有1个比它
: 小；1的右边0个比它小.
: 返回2 1 1=4
: 有没有什么好方法呀？
: 谢谢
|
l**o
发帖数: 356 | 4 我是想用bst，每个节点存包含该节点在内的左子树的大小，如果新的节点插入时，比
它小的节点数就是一路下来比他小的节点记数的和
但是这样最好也是nlgn,弄不好的话n*n，除非用avl
想问问有什么好方法 |
I******c
发帖数: 163 | 5 这个是不是就是求逆序对的数目啊？ 用merge sort 就可以了。 |
j**7
发帖数: 143 | 6 O(N) time
int solution(int[] A) {
if (A == null || A.length == 0) {
return 0;
}
int total = 0;
int[] DP = new int[A.length];
// stores index of the nearest element to the right that is smaller
than A[i]
int[] smaller = new int[A.length];
smaller[A.length - 1] = -1;
for (int i = A.length - 2; i >= 0; i--) {
int index = i + 1;
while (index != -1 && A[i] <= A[index]) {
index = smaller[index];
}
if (index != -1) {
DP[i] = DP[index] + 1;
total += DP[i];
}
smaller[i] = index;
}
return total;
} |
l**o
发帖数: 356 | 7 谢谢，这个比bst的好多了
这个是不是就是求逆序对的数目啊？ 用merge sort 就可以了。
【在 I******c 的大作中提到】
: 这个是不是就是求逆序对的数目啊？ 用merge sort 就可以了。
|
l********6
发帖数: 129 | 8 这难道不是O(n^2)么？？？
smaller
【在 j**7 的大作中提到】
: O(N) time
: int solution(int[] A) {
: if (A == null || A.length == 0) {
: return 0;
: }
: int total = 0;
: int[] DP = new int[A.length];
: // stores index of the nearest element to the right that is smaller
: than A[i]
: int[] smaller = new int[A.length];
|
l********6
发帖数: 129 | 9 哟西~~
【在 I******c 的大作中提到】
: 这个是不是就是求逆序对的数目啊？ 用merge sort 就可以了。
|
j**7
发帖数: 143 | 10 是O(N)因为数组A 的每个index只查看一次
【在 l********6 的大作中提到】
: 这难道不是O(n^2)么？？？
:
: smaller
|
|
|
l********6
发帖数: 129 | 11 你的内循环不算数么？你那个while loop做的事情还是在sorted array里面从大到小顺
序查找一个upperbound啊
【在 j**7 的大作中提到】
: 是O(N)因为数组A 的每个index只查看一次
|
j**7
发帖数: 143 | 12 我错了。 我用DP的算法不对，还是得用merge sort.
想不出O(N)的算法。
【在 l********6 的大作中提到】
: 这难道不是O(n^2)么？？？
:
: smaller
|
j**7
发帖数: 143 | 13 我错了。 我用DP的算法不对，还是得用merge sort.
想不出O(N)的算法。
【在 l********6 的大作中提到】
: 这难道不是O(n^2)么？？？
:
: smaller
|
j**7
发帖数: 143 | 14 内循环+外循环 还是O(N).我本来想用LeetCode Largest Histogram 那道题的DP算法
来解这道题。不过看来用DP不对。
【在 l********6 的大作中提到】
: 你的内循环不算数么？你那个while loop做的事情还是在sorted array里面从大到小顺
: 序查找一个upperbound啊
|
l********6
发帖数: 129 | 15 为什么是O(n)？你的while loop并不能保证每次查找upperbound的时间达到O(1)啊，你
的smaller存的是每一个A[i]的upperbound，但是每次查找的过程都是顺着smaller里面
存的下标往前找，直到找到第一个A[index]可以满足A[i] > A[indx]，这是线性不是常
量的复杂度啊，方便的话求详解~~
【在 j**7 的大作中提到】
: 内循环+外循环 还是O(N).我本来想用LeetCode Largest Histogram 那道题的DP算法
: 来解这道题。不过看来用DP不对。
|
j**7
发帖数: 143 | 16 https://leetcode.com/problems/largest-rectangle-in-histogram/
【在 l********6 的大作中提到】
: 为什么是O(n)？你的while loop并不能保证每次查找upperbound的时间达到O(1)啊，你
: 的smaller存的是每一个A[i]的upperbound，但是每次查找的过程都是顺着smaller里面
: 存的下标往前找，直到找到第一个A[index]可以满足A[i] > A[indx]，这是线性不是常
: 量的复杂度啊，方便的话求详解~~
|
I******c
发帖数: 163 | 17 其实这道题我感觉最好的结果就是O(lgn*n)了
因为如果是O（n)的话，我们就可以在O(n)时间内找到每个元素在数组里的rank，实际
上我们就可以用O(n)排序了。但是理论上排序的最好结果（基于比较的）是O(n*lgn). |
l********6
发帖数: 129 | 18 好吧，我以为你的code已经解决了问题 所以才一直以为是
o(n^2)，仔细看了看
，的确是O(n)，只是答案不太对
【在 j**7 的大作中提到】
: https://leetcode.com/problems/largest-rectangle-in-histogram/
|
l********6
发帖数: 129 | 19 是的，因为其实就是在模拟插入排序，所以不太可能达到线性
【在 I******c 的大作中提到】
: 其实这道题我感觉最好的结果就是O(lgn*n)了
: 因为如果是O（n)的话，我们就可以在O(n)时间内找到每个元素在数组里的rank，实际
: 上我们就可以用O(n)排序了。但是理论上排序的最好结果（基于比较的）是O(n*lgn).
|
c*******t
发帖数: 123 | 20 用两个stack, best case 可以O(n)
第一个stack 不变量是：递增，所有元素比当前元素小。
第二个 stack不变量是：递减，所有元素比当前元素大。
比如 2 8 5 2 6 1
指针指向6时，stack 1: 1. stack2:empty output stack1.size();
指针指向2时， stack1: 1,6, stack2:empty. 6入 stack2, output stack1.size().
2 入stack1
stack1:1,2 stack2:6
省略。。。。。。
指针指向8时， stack1: 1,2,5 stack2: 6, rebalance stack, 6入1.
stack1: 1,2,5,6 stack2:empty
stack1:1,2,5,6,8, stack2:empty
最后指向2： rebalance stack, stack1:1 stack2: 8,6,5,2, output stack1.
size()
【在 l**o 的大作中提到】
: 给一个数组，比如【5，2，6，1】
: 对于5，它的右边有两个数字比它小；对于2，它的右边有一个比小；6的右边有1个比它
: 小；1的右边0个比它小.
: 返回2 1 1=4
: 有没有什么好方法呀？
: 谢谢
|
