新手学习 react 迷惑的点(也可以复习,建议收藏!)

thbcm阅读(380)

网上各种言论说 React 上手比 Vue 难,可能难就难不能深刻理解 JSX,或者对 ES6 的一些特性理解得不够深刻,导致觉得有些点难以理解,然后说 React 比较难上手,还反人类啥的,所以我打算写两篇文章来讲新手学习 React 的时候容易迷惑的点写出来。

为什么要引入 React

在写 React 的时候,你可能会写类似这样的代码:

import React from 'react'


function A() {
  // ...other code
  return <h1>前端桃园</h1>
}

你肯定疑惑过,下面的代码都没有用到 React,为什么要引入 React 呢?

如果你把 import React from ‘react’ 删掉,还会报下面这样的错误:

那么究竟是哪里用到了这个 React,导致我们引入 React 会报错呢,不懂这个原因,那么就是 JSX 没有搞得太明白。

你可以讲上面的代码(忽略导入语句)放到在线 babel 里进行转化一下,发现 babel 会把上面的代码转化成:

function A() {
  // ...other code
  return React.createElement("h1", null, "前端桃园");
}

因为从本质上讲,JSX 只是为 React.createElement(component, props, ...children) 函数提供的语法糖。

为什么要用 className 而不用 class

  1. React 一开始的理念是想与浏览器的 DOM API 保持一直而不是 HTML,因为 JSX 是 JS 的扩展,而不是用来代替 HTML 的,这样会和元素的创建更为接近。在元素上设置 class 需要使用 className 这个 API:
   const element = document.createElement("div")
   element.className = "hello" 

  1. 浏览器问题,ES5 之前,在对象中不能使用保留字。以下代码在 IE8 中将会抛出错误:
   const element = {
    attributes: {
      class: "hello"
    }
   } 

  1. 解构问题,当你在解构属性的时候,如果分配一个 class 变量会出问题:
   const { class } = { class: 'foo' } // Uncaught SyntaxError: Unexpected token }
   const { className } = { className: 'foo' } 
   const { class: className } = { class: 'foo' } 

其他讨论可见:有趣的话题,为什么jsx用className而不是class

为什么属性要用小驼峰

因为 JSX 语法上更接近 JavaScript 而不是 HTML,所以 React DOM 使用camelCase(小驼峰命名)来定义属性的名称,而不使用 HTML 属性名称的命名约定。

来自 JSX 简介

为什么 constructor 里要调用 super 和传递 props

这是官网的一段代码,具体见:状态(State) 和 生命周期

class Clock extends React.Component {
  constructor(props) {
    super(props);
    this.state = {date: new Date()};
  }


  render() {
    return (
      <div>
        <h1>Hello, world!</h1>
        <h2>It is {this.state.date.toLocaleTimeString()}.</h2>
      </div>
    );
  }
}

而且有这么一段话,不仅让我们调用 super 还要把 props 传递进去,但是没有告诉我们为什么要这么做。

不知道你有没有疑惑过为什么要调用 super 和传递 props,接下来我们来解开谜题吧。

为什么要调用 super

其实这不是 React 的限制,这是 JavaScript 的限制,在构造函数里如果要调用 this,那么提前就要调用 super,在 React 里,我们常常会在构造函数里初始化 state,this.state = xxx ,所以需要调用 super。

为什么要传递 props

你可能以为必须给 super 传入 props,否则 React.Component 就没法初始化this.props:

class Component {
  constructor(props) {
    this.props = props;
    // ...
  }
}

不过,如果你不小心漏传了 props,直接调用了 super(),你仍然可以在 render和其他方法中访问 this.props(不信的话可以试试嘛)。

为啥这样也行?因为React 会在构造函数被调用之后,会把 props 赋值给刚刚创建的实例对象:

const instance = new YourComponent(props);
instance.props = props;

props 不传也能用,是有原因的。

但这意味着你在使用 React 时,可以用 super() 代替 super(props) 了么?

那还是不行的,不然官网也不会建议你调用 props 了,虽然 React 会在构造函数运行之后,为 this.props 赋值,但在 super() 调用之后与构造函数结束之前,this.props 仍然是没法用的。

// Inside React
class Component {
  constructor(props) {
    this.props = props;
    // ...
  }
}


// Inside your code
class Button extends React.Component {
  constructor(props) {
    super(); //  忘了传入 props
    console.log(props); //  {}
    console.log(this.props); //  undefined
  }
  // ...
}

要是构造函数中调用了某个访问 props 的方法,那这个 bug 就更难定位了。因此我强烈建议始终使用super(props),即使这不是必须的:

class Button extends React.Component {
  constructor(props) {
    super(props); //  We passed props
    console.log(props); //  {}
    console.log(this.props); //  {}
  }
  // ...
}

上面的代码确保 this.props 始终是有值的。

如果你想避免以上的问题,你可以通过class 属性提案 来简化代码:

class Clock extends React.Component {
  state = {date: new Date()};


  render() {
    return (
      <div>
        <h1>Hello, world!</h1>
        <h2>It is {this.state.date.toLocaleTimeString()}.</h2>
      </div>
    );
  }
}

更详细的内容可见Dan 的博客

为什么组件用大写开头

前面以及说过了,JSX 是 React.createElement(component, props, …children) 提供的语法糖,component 的类型是:string/ReactClass type,我们具体看一下在什么情况下会用到 string 类型,什么情况下用到 ReactClass type 类型

  • string 类型react会觉得他是一个原生dom节点
  • ReactClass type 类型 自定义组件

例如(string):在 jsx 中我们写一个

<div></div>

转换为js的时候就变成了

React.createElement("div", null)

例如(ReactClass type):在jsx中我们写一个

function MyDiv() {
    return (<div><div>)
}

转换为js的时候就变成了

function MyDiv() {
  return React.createElement("div", null);
}


React.createElement(MyDiv, null);

上边的例子中如果将MyDiv中的首字母小写,如下

function myDiv() {
    return (<div><div>)
}

转换为 js 的时候就变成了

function MyDiv() {
  return React.createElement("div", null);
}


React.createElement("myDiv", null);

由于找不到 myDiv 这个 dom,所以就会报错。

为什么调用方法要 bind this

前提知识:深刻的理解 JavaScript 中的 this

相信刚写 React 的时候,很多朋友可能会写类似这样的代码:

class Foo extends React.Component {
  handleClick () {
    this.setState({ xxx: aaa })
  }


  render() {
    return (
      <button onClick={this.handleClick}>
        Click me
      </button>
    )
  }
}

发现会报 this 是 undefined 的错,然后可能对事件处理比较疑惑,然后去看官网的事件处理有下面一段话:

你必须谨慎对待 JSX 回调函数中的 this,在 JavaScript 中,class 的方法默认不会绑定this。如果你忘记绑定 this.handleClick 并把它传入了 onClick,当你调用这个函数的时候 this 的值为 undefined。

这并不是 React 特有的行为;这其实与 JavaScript 函数工作原理有关。通常情况下,如果你没有在方法后面添加 (),例如 onClick={this.handleClick},你应该为这个方法绑定 this。

然后你看了官网的例子和建议之后,知道需要为事件处理函数绑定 this就能解决,想下面这样:

class Foo extends React.Component {
  handleClick () {
    this.setState({ xxx: aaa })
  }


  render() {
    return (
      <button onClick={this.handleClick.bind(this)}>
        Click me
      </button>
    )
  }
}

但是可能你没有去思考过为什么需要 bind this?如果你不能理解的话,还是 js 的基础没有打好。

React 是如何处理事件的?

咱们先来了解一下 React 是如何处理事件的。

React 的事件是合成事件, 内部原理非常复杂,我这里只把关键性,可以用来解答这个问题的原理部分进行介绍即可(后面应该会写一篇 react 的事件原理,敬请期待)。

上篇文章已经说过,jsx 实际上是 React.createElement(component, props, …children) 函数提供的语法糖,那么这段 jsx 代码:

 <button onClick={this.handleClick}>
     Click me
 </button>

会被转化为:

React.createElement("button", {
     onClick: this.handleClick
}, "Click me")

了解了上面的,然后简单的理解 react 如何处理事件的,React 在组件加载(mount)和更新(update)时,将事件通过 addEventListener 统一注册到 document 上,然后会有一个事件池存储了所有的事件,当事件触发的时候,通过 dispatchEvent 进行事件分发。

所以你可以简单的理解为,最终 this.handleClick 会作为一个回调函数调用。

理解了这个,然后再来看看回调函数为什么就会丢失 this。

this 简单回顾

在函数内部,this的值取决于函数被调用的方式。

如果你不能理解上面那句话,那么你可能需要停下来阅读文章,去查一下相关资料,否则你可能看不懂下面的,如果你懒的话,就看为你准备好的 MDN 吧。

通过上面对事件处理的介绍,来模拟一下在类组件的 render 函数中, 有点类似于做了这样的操作:

class Foo {
    sayThis () {
         console.log(this); // 这里的 `this` 指向谁?
     }


     exec (cb) {
         cb();
     }


    render () {
         this.exec(this.sayThis);
  }
}


var foo = new Foo();
foo.render(); // 输出结果是什么?

你会发现最终结果输出的是 undefined,如果你不理解为什么输出的是 undefined,那么还是上面说的,需要去深刻的理解 this 的原理。如果你能理解输出的是undefined,那么我觉得你就可以理解为什么需要 bind this 了。

那么你可能会问:为什么React没有自动的把 bind 集成到 render 方法中呢?在 exec 调用回调的时候绑定进去,像这样:

class Foo {
    sayThis () {
         console.log(this); // 这里的 `this` 指向谁?
     }


     exec (cb) {
         cb().bind(this);
     }


    render () {
         this.exec(this.sayThis);
  }
}


var foo = new Foo();
foo.render(); // 输出结果是什么?

因为 render 多次调用每次都要 bind 会影响性能,所以官方建议你自己在 constructor 中手动 bind 达到性能优化。

四种事件处理对比

对于事件处理的写法也有好几种,咱们来进行对比一下:

1. 直接 bind this 型

就是像文章开始的那样,直接在事件那里 bind this

class Foo extends React.Component {
  handleClick () {
    this.setState({ xxx: aaa })
  }


  render() {
    return (
      <button onClick={this.handleClick.bind(this)}>
        Click me
      </button>
    )
  }
}

优点:写起来顺手,一口气就能把这个逻辑写完,不用移动光标到其他地方。

缺点:性能不太好,这种方式跟 react 内部帮你 bind 一样的,每次 render 都会进行 bind,而且如果有两个元素的事件处理函数式同一个,也还是要进行 bind,这样会多写点代码,而且进行两次 bind,性能不是太好。(其实这点性能往往不会是性能瓶颈的地方,如果你觉得顺手,这样写完全没问题)

2. constuctor 手动 bind 型

class Foo extends React.Component {
  constuctor(props) {
    super(props)
    this.handleClick = this.handleClick.bind(this)
  }
  handleClick () {
    this.setState({ xxx: aaa })
  }


  render() {
    return (
      <button onClick={this.handleClick}>
        Click me
      </button>
    )
  }
}

优点:相比于第一种性能更好,因为构造函数只执行一次,那么只会 bind 一次,而且如果有多个元素都需要调用这个函数,也不需要重复 bind,基本上解决了第一种的两个缺点。

缺点:没有明显缺点,硬要说的话就是太丑了,然后不顺手(我觉得丑,你觉得不丑就这么写就行了)。

3. 箭头函数型

class Foo extends React.Component {
  handleClick () {
    this.setState({ xxx: aaa })
  }


  render() {
    return (
      <button onClick={(e) => this.handleClick(e)}>
        Click me
      </button>
    )
  }
}

优点:顺手,好看。

缺点:每次 render 都会重复创建函数,性能会差一点。

4. public class fields 型

这种 class fields还处于实验阶段,据我所知目前还没有被纳入标准,具体可见这里。

class Foo extends React.Component {
  handleClick = () => {
    this.setState({ xxx: aaa })
  }


  render() {
    return (
      <button onClick={this.handleClick}>
        Click me
      </button>
    )
  }
}

优点:好看,性能好。

缺点:没有明显缺点,如果硬要说可能就是要多装一个 babel 插件来支持这种语法。

总结

我平时用的就这四种写法,我这边从代码的美观性、性能以及是否顺手方便对各种写法做了简单的对比。其实每种方法在项目里用都是没什么问题的,性能方面基本上可以忽略,对于美观性和顺手比较主观,所以总体来说就是看大家的偏好咯,如果硬要推荐的话,我还是比较推荐第四种写法,美观而且不影响性能。

为什么要 setState,而不是直接 this.state.xx = oo

这个问题是我们公司后端写 React 的时候提出的问题,为啥不能直接修改 state,要 setState 一下。我在想,从 vue 转到 React 可能也会有这种疑问,因为 vue 修改状态都是直接改的。

如果我们了解 setState 的原理的话,可能就能解答这个问题了,setState 做的事情不仅仅只是修改了 this.state 的值,另外最重要的是它会触发 React 的更新机制,会进行 diff ,然后将 patch 部分更新到真实 dom 里。

如果你直接 this.state.xx == oo 的话,state 的值确实会改,但是改了不会触发 UI 的更新,那就不是数据驱动了。

那为什么 Vue 直接修改 data 可以触发 UI 的更新呢?因为 Vue 在创建 UI 的时候会把这些 data 给收集起来,并且在这些 data 的访问器属性 setter 进行了重写,在这个重写的方法里会去触发 UI 的更新。如果你想更多的了解 vue 的原理,可以去购买染陌大佬的剖析 Vue.js 内部运行机制。

不明白访问器属性的可以看这篇文章:深入理解JS里的对象

setState 是同步还是异步相关问题

1. setState 是同步还是异步?

我的回答是执行过程代码同步的,只是合成事件和钩子函数的调用顺序在更新之前,导致在合成事件和钩子函数中没法立马拿到更新后的值,形式了所谓的“异步”,所以表现出来有时是同步,有时是“异步”。

2. 何时是同步,何时是异步呢?

只在合成事件和钩子函数中是“异步”的,在原生事件和 setTimeout/setInterval等原生 API 中都是同步的。简单的可以理解为被 React 控制的函数里面就会表现出“异步”,反之表现为同步。

3. 那为什么会出现异步的情况呢?

为了做性能优化,将 state 的更新延缓到最后批量合并再去渲染对于应用的性能优化是有极大好处的,如果每次的状态改变都去重新渲染真实 dom,那么它将带来巨大的性能消耗。

4. 那如何在表现出异步的函数里可以准确拿到更新后的 state 呢?

通过第二个参数 setState(partialState, callback) 中的 callback 拿到更新后的结果。

或者可以通过给 setState 传递函数来表现出同步的情况:

this.setState((state) => {
    return { val: newVal }
})

5. 那表现出异步的原理是怎么样的呢?

直接讲源码肯定篇幅不够,可以看这篇文章:你真的理解setState吗?。

我这里还是用最简单的语言让你理解:在 React 的 setState 函数实现中,会根据 isBatchingUpdates(默认是 false) 变量判断是否直接更新 this.state 还是放到队列中稍后更新。然后有一个 batchedUpdate 函数,可以修改 isBatchingUpdates 为 true,当 React 调用事件处理函数之前,或者生命周期函数之前就会调用 batchedUpdate 函数,这样的话,setState 就不会同步更新 this.state,而是放到更新队列里面后续更新。

这样你就可以理解为什么原生事件和 setTimeout/setinterval 里面调用 this.state 会同步更新了吧,因为通过这些函数调用的 React 没办法去调用 batchedUpdate 函数将 isBatchingUpdates 设置为 true,那么这个时候 setState 的时候默认就是 false,那么就会同步更新。

最后

setState 是 React 非常重要的一个方法,值得大家好好去研究一下他的原理。

以上就是W3Cschool编程狮关于新手学习 react 迷惑的点(也可以复习,建议收藏!)的相关介绍了,希望对大家有所帮助。

关于 缓存穿透/缓存击穿/缓存雪崩 看这篇文章就够了

thbcm阅读(413)

国庆加中秋过去了,大家准备好学习了么?

redis 在项目中用的话,主要就是用作缓存了

既然用作缓存,那就肯定会有 缓存穿透/缓存击穿/缓存雪崩 的问题

这篇文章就来说说,遇到这种情况时,该如何去处理

缓存穿透

首先咱们搞明白什么是缓存穿透?这三个词这么像,得把概念搞清楚不是

其实只是从字面意思上来看的话,大概也能知道一点儿,缓存穿透嘛,就是直接穿过了缓存,将请求打到了数据库上面去

一般情况下,去查询数据的话,缓存里面应该都是有的,但是防不住黑客呀,如果黑客请求查询的是数据库里面根本不存在的数据,数据库里面都没有的数据,缓存里面肯定也不会有了,对吧,那么此时请求就会打到咱们的数据库里面去,这就是缓存穿透

你想啊,黑客想要攻击的话,怎么可能只请求一次呢,肯定是大量的请求过来,因为是拿数据库里面不存在的 id 来请求的,那么这些请求毫无疑问直接打到了数据库上面去,那咱们的数据库可能就会因为这些大量的请求直接宕掉

如何解决呢?

咱们回到产生这个问题的场景中,为什么大量的请求会打到数据库上面来?因为缓存里面没有对应的 key 对吧,所以才会越过缓存直接到数据库

那么问题就好解决了嘛,缓存里面没有对应的 key ?OK ,如果这个 key 数据库里面也没有,那我就在 redis 里面,存上这个 key ,值是 null ,这样如果有查询这个 key 的请求,我直接返回 null 就完事儿了,也就不用打到数据库上面去了

注意一下,要记得设置它的过期时间,一般三到五分钟就够了

但是对方是个黑客呀,可能就用一个 key 去请求么?他可能会在短时间内用大量的 key 来发送请求,那如果一个 key 就在 redis 中存储一个 null 值的话,那么多 key 是不是就会存储那么多个 null 值嘞?

这样的话, redis 里面是不是都是值为 null 的了?

所以有没有更好的解决办法呢?

那必须得有!布隆过滤器,你值得尝试

什么是布隆过滤器呢?就是它能告诉你,某个值一定不存在或者可能存在( emmmm ,也不知道我有没有说清楚

所以可以将数据库的内容缓存一份到布隆过滤器,这样的话,当大量的请求过来的时候, redis 里面没有,没关系,再去布隆过滤器过滤一下,这样请求不用打到数据库上面去,就能确定这个 key 数据库中有没有

这样不就降低了数据库的压力么,可真是个天才~

缓存击穿

缓存击穿说的是,在高并发情况下,如果好多个请求都在查询一个 key ,好巧不巧的是,这个 key 因为某些原因失效了(比如设置的过期时间到了,缓存服务器宕机了),这样就会导致那么多的请求都直接打到数据库上面去了

那如果这些请求的数量足够大的话,可能直接把数据库就干掉了

知道了造成结果的原因,那么寻找解决方案也就好办了

不是因为好多个请求打到了数据库嘛,但是它们请求的都只是一个 key ,所以这里可以使用排斥锁来实现,第一个请求达到请求 key 发现缓存里面没有,允许它去数据库查询,同时加锁,这样第二个请求,第三个请求…都会被锁阻塞到当前,不会再打到数据库,这样就减少了数据库的并发压力

缓存雪崩

缓存雪崩,雪崩雪崩嘛,就比较严重,击穿说的是一个 key 失效的情况,雪崩指的是大规模的缓存失效情况的发生,这是有可能发生的,比如说我的缓存服务器宕机了,那是不是直接就大规模的缓存失效了;或者说,我当时为了图省事,好多个 key 设置的过期时间都是一样的,然后刚好在缓存都失效的时候,好多请求不同的 key 过来了

解决方案的话,其实就不适合使用加锁的方式去解决了,因为这是好多请求不同的 key ,它不是一个嘛

而且嘞,咱们是因为好多个 key 设置的过期时间都是一样的,所以解决方案就是,咱们不设置同样的时间让缓存失效了,咱们给一个随机时间,让缓存随机失效,这样的话,大规模的缓存失效情况就减少很多了

那还要一种情况呢,就是如果我的缓存服务器直接宕机了,这怎么办?也好弄,来个集群就解决了,这里只是一个解决方案,它的落地实现不是本文重点哈~

再谈 布隆过滤器

OK ,你如果看到这里的话,其实这篇文章的内容就说完了

但是我感觉布隆过滤器那块,我没有说清楚,所以在这里拿出来详细说一说(我知道你一定又在默默夸阿粉是个暖男了,乖,知道就好了,不要真说出来,我会害羞的

布隆过滤器是一种数据结构,它是一种概率型的数据结构,就是它能告诉你“某样东西一定不存在或者可能存在”

你可能会说,这话刚刚不是说过了嘛,本来就挺拗口的,你咋还说

还不是因为这句话比较重要,我觉得把这句话理解透彻了,那么对布隆过滤器理解的应该也就到位了

来,为了形象生动一些,咱们举个例子~ 布隆过滤器是一个 bit 向量或者说 bit 数组,大概长这样:

现在,我们需要把 “AliPay” 这个字段给存储进去 大概的存储过程就是:将要映射的值,使用多个不同的哈希函数生成多个哈希值,然后每个生成的哈希值指向的 bit 置为 1

以给的为例,我们现在将 “AliPay” 这个值,通过三个不同的哈希函数进行映射,那么大概就是这样了:

同样,现在我要存储另外一个值 “WechatPay” ,那么可能映射之后就是下面这样:

细心的你可能就会发现, 4 号位置的值,刚开始不是给 “AliPay” 了么,后来 “WechatPay” 也在那里,这样的话,值不就给覆盖掉了嘛

嗯,没错,是被覆盖掉了

接下来,我们查询 “Ali” 那么查询之后,布隆过滤器可能会给你 “0,1,2” 的值, 结果呢 “2” 的位置是 0 ,说明没有任何值映射到这个位置上来,所以我们就可以判定数据库里面没有 “Ali” 这个值

那我查询 “AliPay” 的话,毫无疑问,肯定会返回给我 “1,4,6” ,那我们能说数据库里面一定有 “AliPay” 么?不能,因为 “1,4,6” 的值有可能被其他的值给覆盖到了,所以我们只能说,数据库里可能存在 “AliPay”

这就是布隆过滤器说的”某个值一定不存在或者可能存在”

乖,你懂了吗?

文章来源于公众号:Java极客技术 作者:鸭血粉丝

以上就是W3Cschool编程狮关于关于 缓存穿透/缓存击穿/缓存雪崩 看这篇文章就够了的相关介绍了,希望对大家有所帮助。

算法图解:如何找出栈中的最小值?

thbcm阅读(411)

前面我们学习了很多关于栈的知识,比如《动图演示:手撸堆栈的两种实现方法!》和《JDK 竟然是这样实现栈的?》,那么接下来我们再来刷一些关于栈的经典面试题以巩固学过的知识。

我们今天的面试题是这样的…

题目

定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.min(); –> 返回 -3.

minStack.pop();

minStack.top(); –> 返回 0.

minStack.min(); –> 返回 -2.

LeetCode 地址:https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/

思考

首先来说这道题目本身很好理解,它的实现难点在于以下两个方面:

  • 当我们进行 pop(移除栈顶元素)操作时如果删除的是当前最小值,那么我们如何寻找下一个最小值?
  • 要保证调用 min、push 及 pop 的时间复杂度都是 O(1)。

也就是说,在我们执行了 pop 时如果移除的栈中最小的值,那么如何寻找栈中的下一个最小元素?并且要保证操作的时间复杂度为 O(1)。这个时间复杂度制约了我们在移除了最小值之后不能通过遍历查找下一个最小值,所以这就成为了这道题的难点。

比如当我们移除以下栈顶元素值:

因为最小值就是 1,因此在移除之后最小值也被移除了,如下图所示:

那么接下来,让我们一起思考 3 分钟,想一想应该如何处理这个问题~

解题思路

其实我们可以在每次入栈时,判断当前元素是否小于最小值,如果小于则将原最小值和最新的最小值相继入栈,这样在调用 pop 时即使移除的是最小值,我们也能通过获取下一个元素得到一个新的最小值,执行流程如下所示。

操作步骤1

入栈第一个元素,因为是第一个元素,因此最小值就是此元素的值。

操作步骤2

入栈第二个元素,如下图所示:

因为入栈的元素 3 比 8 小,所以先将栈中的原最小值 8 存入栈中,再将 3 入栈。

操作步骤3

入栈第三个元素,如下图所示:

因为入栈元素 5 大于 3,因此栈中的最小值不变,直接将元素 5 入栈。

操作步骤4

继续入栈,如下图所示:

入栈元素 1 小于于 3,因此先将原最小值 3 入栈,再将 1 入栈,栈中的最小值更改为 1。

操作步骤5

执行出栈操作,如下图所示:

元素 1 出栈,判断当前元素就是栈的最小值,因此将栈顶元素 3 设置为最小值,并移除元素 3,如下图所示:

操作步骤6

继续出栈,如下图所示:

因为元素 5 不是当前最小值,因此直接出栈。

操作步骤7

继续出栈,如下图所示:

因为出栈元素 3 为最小值,因此继续将最小值设置为栈顶元素 8,并将栈顶元素出栈,如下图所示:

这样就剩下最后一个元素了,最后一个元素出栈之后就成空栈了,整个流程就执行完了。

实现代码1

接下来我们将上面的思路用代码实现一下,我们用数组实现的栈来实现相关的功能,代码如下:

class MinStack {
    private int[] data; // 栈数据
    private int maxSize; // 最大长度
    private int top; // 栈顶指针(下标)
    private int min; // 最小值


    // 构造函数
    public MinStack() {
        // 设置默认值
        maxSize = 10000;
        data = new int[maxSize];
        top = -1;
        min = Integer.MAX_VALUE;
    }


    // 入栈(添加元素)
    public void push(int x) {
        if (min >= x) {
            // 遇到了更小的值,记录原最小值(入栈)
            data[++top] = min;
            min = x;
        }
        // 当前值入栈
        data[++top] = x;
    }


    // 出栈(移除栈顶元素)
    public void pop() {
        if (min == data[top]) {
            min = data[--top]; // 拿到原最小值,并(将原最小值)出栈
        }
        --top; // 出栈
    }


    // 查找栈顶元素
    public int top() {
        return data[top];
    }

 
    // 查询最小值
    public int min() {
        return min;
    }
}

上述代码在 LeetCode 的执行结果如下:

可以看出性能还是很高的,超越了 99.92% 的用户,内存消耗也不大。它的核心代码在 push 方法内,先将原最小值和最新最小值相继入栈,在 pop 出栈时判断出栈元素是否为最小值,如果是最小值则将当前最小值指向栈顶元素并将栈顶元素出栈,这样就得到了下一个新的最小值了。

实现代码2

如果我们不想使用数组的自定义栈来实现,还可以使用 Java 中自带的栈 Stack 来实现此功能,代码如下:


class MinStack {
    private Stack stack = new Stack();
    private int min = Integer.MAX_VALUE;


    public MinStack() { }


    // 入栈(添加元素)
    public void push(int x) {
        if (x  这种实现代码的方式(使用 Java API),在刷题或者实际面试中如果没有特殊说明是可以直接用的。


### 总结


本文我们通过两种方式:自定义数组栈和 Java API 中的 `Stack` 来实现了栈中最小值的功能,保证了在调用栈的 min、push 及 pop 方法时的时间复杂度都是 O(1)。两种实现方式的代码虽然略不相同,但实现思路都是一样的,都是**在元素入栈时判断当前元素是否小于最小元素,如果小于最小元素则先将原最小值入栈,再将当前最小元素入栈,这样当调用 pop 方法时,即使移除的是最小值,只需要将下一个元素取出即为新的最小值了**,这样就可以实现调用 min、push 及 pop 方法时的时间复杂度都是 O(1) 了。


>文章来源于公众号:Java中文社群 作者:磊哥


以上就是`W3Cschool编程狮`关于**算法图解:如何找出栈中的最小值?**的相关介绍了,希望对大家有所帮助。

SpringBoot实战:Spring Boot接入Security权限认证服务

thbcm阅读(422)

通过
JWT 为每个用户生成一个唯一且有期限的
Token,用户每次请求都会重新生成过期时间,在规定的时间内,用户未进行操作
Token 就会过期,当用户再次请求时则会再次执行登录流程,而
Token 的过期时间应根据实际的业务场景规定。

java中的HsahMap

thbcm阅读(386)

准备开始学习java了。

今天学习的第五天,每天都会发文章,我要卷起来。

请小伙伴们监督我,奥利给

联系我们