Изображение обрезки CSS в div слева

Принцип динамического программирования очень подробно объясняется Шашанком Джаином. Я хотел бы объяснить, как сделать то же самое с помощью dequeue. Ключ состоит в том, чтобы поддерживать максимальный элемент в верхней части очереди (для окна) и отбрасывать бесполезные элементы, а также отбрасывать элементы, которые находятся вне индекса текущего окна. бесполезные элементы = Если текущий элемент больше, чем последний элемент очереди, то последний элемент очереди бесполезен. Примечание. Мы сохраняем индекс в очереди, а не сам элемент. Это будет более понятно из самого кода. 1. Если текущий элемент больше, чем последний элемент очереди, то последний элемент очереди бесполезен. Нам нужно удалить этот последний элемент. (и продолжать удалять, пока последний элемент очереди не будет меньше текущего элемента). 2. Если current_index - k> = q.front (), значит, мы выходим из окна, поэтому нам нужно удалить элемент из очереди.

vector<int> max_sub_deque(vector<int> &A,int k)
{
    deque<int> q;
    for(int i=0;i<k;i++)
    {
        while(!q.empty() && A[i] >= A[q.back()])
            q.pop_back();
        q.push_back(i);
    }
    vector<int> res;
    for(int i=k;i<A.size();i++)
    {
        res.push_back(A[q.front()]);
        while(!q.empty() && A[i] >= A[q.back()] )
            q.pop_back();
        while(!q.empty() && q.front() <= i-k)
            q.pop_front();
        q.push_back(i); 
    }
    res.push_back(A[q.front()]);
    return res;
}

Поскольку каждый элемент находится в очереди и выгружается с максимальной сложности времени от времени, то O (n + n) = O (2n) = O (n). И размер очереди не может превышать предел k. поэтому пространственная сложность = O (k).