-1

这是我第一次发布问题，如果我做错了什么，请原谅我。我的问题是如何从这段代码中获得更快的算法？我目前正在使用 2 个堆栈来实现代码，这样它将获得用户要求输入的索引范围之外的最小值。

示例（2,3,4,5,1），如果（用户选择（1,4）），则表示他们正在查看（2,3,4,5），输出为2。谢谢。

import java.util.*;

interface StackADT <Integer> {
    // check whether stack is empty
    public boolean empty(); 

    // retrieve topmost item on stack
    public int       peek() throws EmptyStackException;

    // remove and return topmost item on stack
    public int       pop() throws EmptyStackException;

    // insert item onto stack
    public void    push(int item);
}


class StackArr <Integer> implements StackADT <Integer> {
    private int[] arr;
    private int top;
    private int maxSize;
    private final int INITSIZE = 1000;

    public StackArr() {
        arr = (int[]) new int[INITSIZE]; // creating array of type E
        top = -1;  // empty stack - thus, top is not on an valid array element
        maxSize = INITSIZE;
    }

    public boolean empty() { 
        return (top < 0); 
    }

    public int peek() throws EmptyStackException {
        if (!empty()) return arr[top];
        else throw new EmptyStackException();
    }

    public int pop() throws EmptyStackException {
        int obj = peek();
        top--;
        return obj;
    }

    public void push(int obj) {
        if (top >= maxSize - 1) enlargeArr();
        top++;
        arr[top] = obj;
    }
}


class RMQ{

    //declare stack object
    Stack<Integer> stack1;

    public RMQ(){
        stack1 = new Stack<Integer>();
    }

    public void insertInt(int num){
        stack1.push(num);
    }






    public int findIndex(int c, int d){



        Stack<Integer> tempStack = new Stack<Integer>();
        Stack<Integer> popStack = new Stack<Integer>();

        tempStack = (Stack)stack1.clone();

        while (d != tempStack.size())
        {
            tempStack.pop();            
        }

        int minValue = tempStack.pop();
        popStack.push(minValue);
        while (c <= tempStack.size())
        {
            int tempValue = tempStack.pop();
            if(tempValue >= minValue)
            {
                continue;
            }
            else
            {
                popStack.push(tempValue);
                minValue = tempValue;

            }
        }

        return popStack.pop();

    }


}




public class Pseudo{

    public static void main(String[] args){
        //declare variables
        int inputNum;
        int numOfOperations;

        //create object
        RMQ rmq = new RMQ();

        Scanner sc = new Scanner(System.in);

        //read input
        inputNum = sc.nextInt();


        //add integers into stack
        for(int i=0; i < inputNum; i++){
            rmq.insertInt(sc.nextInt());
        }

        // read input for number of queries
        numOfOperations = sc.nextInt();


        // Output queries
        for(int k=0; k < numOfOperations; k++){
           int output = rmq.findIndex(sc.nextInt(), sc.nextInt());
           System.out.println(output);
        }

    }
}
4

3 回答 3

0

我理解您的问题的方式是您想对固定数组进行一些预处理，然后使您对一系列元素的查找最小值操作非常快。

该答案描述了一种方法，该方法执行 O(nlogn) 预处理工作，然后对每个查询进行 O(1) 工作。

预处理 O(nlogn)

这个想法是准备一个二维数组 SMALL[a,k] 其中 SMALL[a,k] 是从 a 开始的 2^k 个元素中的最小值

您可以通过从 k==0 开始以递归方式计算此数组，然后通过将两个先前的元素组合在一起来为每个更高的元素构建值。

SMALL[a,k] = min(SMALL[a,k-1] , SMALL[a+2^(k-1),k-1])

每个查询查找 O(1)

然后，您可以通过组合 2 个预先准备好的答案立即找到任何范围的最小值。

假设您想找到从 100 到 133 的元素的最小值。您已经知道 32 个元素 100 到 131 的最小值（在 BIG[100,5] 中）以及从 102 到 133 的 32 个元素的最小值（在 BIG[102 ,5]) 所以你可以找到其中最小的一个来得到答案。

于 2013-10-18T12:23:39.180 回答
0

这是范围最小查询问题。

有一些算法和数据结构可以有效地解决它

于 2013-10-21T06:33:12.720 回答
0

你为什么使用堆栈？只需使用一个数组：

int[] myArray = new int[inputNum];
// fill the array...

// get the minimum between "from" and "to"
int minimum = Integer.MAX_VALUE;
for(int i = from ; i <= to ; ++i) {
    minimum = Math.min(minimum, myArray[i])
}

就是这样！

于 2013-10-18T11:39:09.923 回答