0

嗨，我需要找到程序的时间和空间复杂度，请帮助，如果可能，请提出可以执行的优化，...................... ..................................................... ..................................................... ..................................................... ......

public class Sol {
    public int findMaxRectangleArea(int [][] as) {
        if(as.length == 0)
       return 0;
    int[][] auxillary = new int[as.length][as[0].length];
        for(int i = 0; i < as.length; ++i) {
            for(int j = 0; j < as[i].length; ++j) {
            auxillary[i][j] = Character.getNumericValue(as[i][j]);
        }
        }
        for(int i = 1; i < auxillary.length; ++i) {
        for(int j = 0; j < auxillary[i].length; ++j) {
            if(auxillary[i][j] == 1)
                    auxillary[i][j] = auxillary[i-1][j] + 1;
            }
        }

    int max = 0;
        for(int i = 0; i < auxillary.length; ++i) {
            max = Math.max(max, largestRectangleArea(auxillary[i]));
        }
        return max;
    }

    private int largestRectangleArea(int[] height) {
        Stack<Integer> stack =
        new Stack<Integer>();
        int max = 0;
        int i = 0;
        while(i < height.length) {
            if(stack.isEmpty() ||
                height[i] >= stack.peek()) {
                stack.push(height[i]);
            i++;
            }
            else {
            int count = 0;
            while(!stack.isEmpty() &&
                stack.peek() > height[i]) {
                    count++;
                    int top = stack.pop();
                max = Math.max(max, top * count);
                }
            for(int j = 0; j < count + 1; ++j) {
                    stack.push(height[i]);
                }
                i++;
            }
        }

        int count = 0;
        while(!stack.isEmpty()) {
            count++;
            max = Math.max(max, stack.pop() * count);
        }
        return max;
    }

先感谢您

4

1 回答 1

1

要查找空间复杂度，请查看您声明的变量并且大于单个原始变量。事实上，我相信您的空间复杂度将由我的数组auxilary和Stack stack. 第一个的大小很清楚，我不完全理解第二个，但我看到它的大小永远不会大于数组的大小。所以我会说空间复杂度是O(size of(auxilary))or O(N * M)where N=as.length()and M = as[0].length。

现在时间复杂度有点棘手。您在整个auxilary数组上有两个周期，因此可以肯定时间复杂度至少为O( N * M). 您还有另一个循环largestRectangleArea调用auxilary. 如果我正确地获得了这个函数中的代码，那么这个函数似乎又是线性的，但我不确定这里。由于您更了解逻辑，因此您可能能够更好地计算其复杂性。

希望这可以帮助。

于 2013-02-08T12:20:29.307 回答