hiho一下第153周《股票价格》题目分析

6
1

《股票价格》题目分析

这道题目要求我们实现一个数据结构可以处理一种二元数据< timestamp, price >。

并其支持以下操作：

  1. 在队尾插入一条数据
  2. 删除timestamp小于等于给定值的数据，根据题意我们知道这些数据都在队首
  3. 查询price最高、最低和timestamp最大(队尾)的数据

其中1和2可以用队列实现，3可以用堆实现。但是我们要把队列和堆结合起来就有点难度。困难在于当我们从队首删除数据的时候，我们必须知道这些数据在堆中的位置，然后才能进行删除。有兴趣的同学可以自己实现一个完整的带索引的堆。

这里我们介绍一种利用set/map的平衡树特性(Java中的TreeMap和TreeSet, C#中的SortedSet和SortedDictionary, Python...)的做法。

首先我们用map<int, int> price来保存每个timestamp的price是多少，也就是price[timestamp]保存着timestamp时的价格。由于map内部是用红黑树实现的，所以我们从price.beign()到price.end()依次保存着timestamp从小到大的数据。

其次我们用multiset<int> prices来保存没被删掉的数据的价格集合。同样由于set/multiset是由红黑树实现的，所以从prices.begin()到prices.end()从小到大一次保存着价格。(有些语言没有内置的多重集合，我们也可以用类似 set<pair<int, int>> 的方式存储，其中pair的第一关键字是price，第二关键字是timestamp。)

当我们遇到P指令时，只需将数据插入price和prices：

if(c == 'P') {
    cin >> t >> p;
    price[t] = p;
    prices.insert(p);
}

当我们遇到删除时，只需要从头开始在price里找timestamp小于等于给定值的数据，然后再在price和prices里同时删除这些数据。虽然一次R操作可能删除掉多条数据，但是均摊下来每次操作只会删除一条数据，复杂度是O(logN)的。

if(c == 'R') {
    cin >> t;
    while(price.size() != 0 && price.begin()->first <= t) {
        auto itr = prices.find(price.begin()->second);
        prices.erase(itr);
        price.erase(price.begin());
    }
}

对于查询，最高价格保存在prices.begin()，最低价格保存在prices.rbegin(), 最近价格保存在price.rbegin()。

if(c == 'Q') {
    cout << *(prices.rbegin()) << ' ' << *(prices.begin()) << ' ' << price.rbegin()->second << endl;
}

10 answer(s)

1

这个题可以用单调队列 O(n)的复杂度

0

写了把Q和R涉及到的P的位置离散化后分块建线段树，离散化O((Q+R) log(Q+R))，分块O(N)，查询O(Qlog(B))（B是块数），用时1191ms……

0

这个题有O(n)做法...

#include<cstdio>
struct node{
    int t,p;
}q1[500005],q2[500005];int head1=0,tail1=0,head2=0,tail2=0;
int recent;
int main(){
    int n;scanf("%d",&n);
    char buf[10];
    int x,y;
    while(n--){
        scanf("%s",buf);
        if(buf[0]=='P'){
            scanf("%d%d",&x,&y);recent=y;
            while(head1!=tail1&&q1[tail1-1].p<y)tail1--;
            q1[tail1].t=x;q1[tail1].p=y;tail1++;
            while(head2!=tail2&&q2[tail2-1].p>y)tail2--;
            q2[tail2].t=x;q2[tail2].p=y;tail2++;
        }else if(buf[0]=='Q'){
            printf("%d %d %d\n",q1[head1].p,q2[head2].p,recent);
        }else{
            scanf("%d",&x);
            while(head1!=tail1&&q1[head1].t<=x)head1++;
            while(head2!=tail2&&q2[head2].t<=x)head2++;
        }
    }
    return 0;
}
0

C#的问题，SortedSet不能保存两个一样的值，我的方法是插入的时候如果有了一样的价格就把之前的时间价格键值对删除，这部的操作是O（n）的，70分就TLE了。有什么更好的解决方法吗。 代码如下：

using System;
using System.Collections.Generic;
using System.Linq;

namespace SharePrice
{
    class Program
    {
        static void Main(string[] args)
        {
            int size = int.Parse(Console.ReadLine());
            Solution price = new Solution();
            for (int i = 0; i < size; i++)
            {
                string[] instruction = Console.ReadLine().Split(' ');
                switch (instruction[0])
                {
                    case "P": price.Insert(int.Parse(instruction[1]), int.Parse(instruction[2])); break;
                    case "R": price.Remove(int.Parse(instruction[1])); break;
                    case "Q": price.Query(); break;
                }
            }
        }
        class Solution
        {
            private SortedDictionary<int, int> prices;
            private SortedSet<int> heap;

            public Solution()
            {
                this.prices = new SortedDictionary<int, int>();
                this.heap = new SortedSet<int>();
            }
            public void Insert(int timestamp, int price)
            {
                prices.Add(timestamp, price);
                if (!heap.Contains(price))
                    heap.Add(price);
                else
                    foreach (var pair in prices)
                    {
                        if (pair.Value == price)
                        {
                            prices.Remove(pair.Key);
                            break;
                        }

                    };
            }
            public void Remove(int timestamp)
            {
                while (prices.First().Key <= timestamp)
                {
                    heap.Remove(prices.First().Value);
                    prices.Remove(prices.First().Key);
                }
            }
            public void Query()
            {
                Console.WriteLine("{0} {1} {2}", heap.Last(), heap.First(), prices.Last().Value);
            }

        }
    }
}

  • 你可存一个Tuple<int, int> 第一个int是price第二个是timestamp。让SortedSet按第一个int排序即可。

  • C#好像没有OrderedSet类，相似的就只有一个OrderedDictionary，这个类自身没有排序功能，用List.Sort排序也是O（n）级别操作。 我后来想了一个方法，就是在查询把SortedSet在查询的方法里定义，然后把SortedDictionary中剩余键值对的值加到SortedSet里面，这样就能保证准确的获得最大最小值。我感觉是没有什么多余的步骤了，但是还是TLE了

  • 我一开始搞错了，是SortedSet。

  • Tuple这个类没有ADD和Remove 的方法，这个要怎么用

  • 我的意思是用SortedSet<Tuple<int, int>>存，这样加了一维timestamp不就没有重复的问题了嘛。

  • 原来是这样子用的，了解了，但是70分还是TLE，这是方法的性能问题吗？

  • 那你可以写分块 线段树 平衡树

  • 添加评论
  • ✖reply
0

一直Time Limit Exceeded

  • 你是怎么做的？ 是不是复杂度太高啊

  • 添加评论
  • ✖reply
0

第一眼就想到线段树，区间查询毫不犹豫就是线段树。感觉上面的方法简单好多好多啊。

0

裸的单点更新，区间查询线段树就好，简单粗暴

2

price没有必要用map，因为输入是保证timestamp升序的，
然后price的值可以保存prices里的迭代器。这样可以避免了查找操作

list<pair<int, set<int>::iterator>> price;

if(c == 'P') {
    cin >> t >> p;
    auto it = prices.insert(p);
    price.emplace_back(make_pair(t, it));
}


if(c == 'R') {
    cin >> t;
    while(price.size() != 0 && price.begin()->first <= t) {
        prices.erase(price.begin()->second);
        price.erase(price.begin());
    }
}
0

输出时如果price里已经没有数据了应该输出什么？

  • 没有这样的数据

  • 好吧，一直卡在80，我以为是这个原因

  • 一开始我也卡在了80分。。。

  • 这是特殊数据10 P 1 77 P 2 73 P 5 74 P 7 74 Q R 4 Q P 8 78 R 6 Q

  • 原因是一开始排序函数只按price排序，这样price一样的时候只会保存前面的那个二元组，解决方案是使用multiset或者是排序时如果price相同，按timestamp排序

  • 添加评论
  • ✖reply
0

开一个set维护pair，设置last变量保存最后一次Price提交，删除时只记录timestamp，查询时检查是否有效，无效则从set里面删掉，有效输出即可~

write answer 切换为英文 切换为中文

转发分享

▲