go的切片实现stack问题

Thomas_Z · 2018-04-29 14:39:47 · 1493 次点击 · 大约8小时之前 开始浏览    置顶
这是一个创建于 2018-04-29 14:39:47 的主题,其中的信息可能已经有所发展或是发生改变。

日常刷题刷到一个要用到栈的问题,go没有内置stack就用切片实现了,然而效率低的过分,不知道是不是我不会用导致的,发给大家看看。

这是golang用时和代码: image.png

这是C艹用时:

image.png C艹代码:


class Solution {
public:
    vector dailyTemperatures(vector& temperatures) {
        int size=temperatures.size();
        vector res(size);
        stack s;
        s.push(size-1);
        for(int i=size-2;i>=0;i--){
            while(!s.empty() && temperatures[s.top()]<=temperatures[i])
                s.pop();
            if(!s.empty())
                res[i]=s.top()-i;
            s.push(i);
        }
        return res;
    }
};

有疑问加站长微信联系(非本文作者)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

1493 次点击  
加入收藏 微博
5 回复  |  直到 2018-04-30 22:08:43
Thomas_Z
Thomas_Z · #1 · 7年之前

按理来说不应该啊,切片不是一个len cap 指针结构体吗?代价不会这么高啊。不过C艹的stack是用链表为底层实现的,还是说这里链表的效率比顺序存储更高?

go没有内置链表类型吧@.@?

Thomas_Z
Thomas_Z · #2 · 7年之前

诶?万恶的html语法把<int>吞了……懒得转义了不是重点~

AceDarkkinght
AceDarkkinght · #3 · 7年之前

slice 的底层实现是数组,append 时如果数组容量不够会进行扩容影响性能。不过你的代码慢应该不是扩容导致的。 没记错的话 container/list go 内置的双向链表

Thomas_Z
Thomas_Z · #4 · 7年之前
AceDarkkinghtAceDarkkinght #3 回复

slice 的底层实现是数组,append 时如果数组容量不够会进行扩容影响性能。不过你的代码慢应该不是扩容导致的。 没记错的话 container/list go 内置的双向链表

好嗒,学到了。

jarlyyn
jarlyyn · #5 · 7年之前

这操作感觉有点骚…………

切应该是数组吧?

虽然没测试过,但按常理,对切片append的话,应该是整个复制出来的吧。

不然切片没切到尾的话怎么操作。

记得当年学C的时候,stack应该是用链表实现的吧?

添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传